#P1005. [NOIP2010普及组] 导弹拦截

news/2024/4/21 0:20:41/

题目描述

经过 1111年的韬光养晦,某国研发出了一种新的导弹拦截系统,凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为 00时,则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷:每套系统每天只能设定一次工作半径。而当天的使用代价,就是所有系统工作半径的平方和。

某天,雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段,所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹,请计算这一天的最小使用代价。

输入格式

第一行包含 44个整数x_1x1​、y_1y1​、x_2x2​、y_2y2​,每两个整数之间用一个空格隔开,表示这两套导弹拦截系统的坐标分别为(x_1, y_1)(x1​,y1​)、(x_2, y_2)(x2​,y2​)。 第二行包含11 个整数NN,表示有 NN颗导弹。接下来NN行,每行两个整数 x,yx,y,中间用 一个空格隔开,表示一颗导弹的坐标(x, y)(x,y)。不同导弹的坐标可能相同。

输出格式

一个整数,即当天的最小使用代价。

输入数据 1

0 0 10 0
2
-3 3
10 0

Copy

输出数据 1

18

Copy

输入数据 2

0 0 6 0
5
-4 -2
-2 3
4 0
6 -2
9 1

Copy

输出数据 2

30

Copy

提示

两个点(x_1, y_1)(x1​,y1​)、(x_2, y_2)(x2​,y2​)之间距离的平方是(x_1-x_2)^2+(y_1-y_2)^2(x1​−x2​)2+(y1​−y2​)2。

两套系统工作半径r_1,r_2r1​,r2​的平方和,是指 r_1,r_2r1​,r2​ 分别取平方后再求和,即 r_1^2+r_2^2r12​+r22​。

【样例 11说明】

样例11中要拦截所有导弹,在满足最小使用代价的前提下,两套系统工作半径的平方分别为1818和00。

【样例22 说明】

样例22中的导弹拦截系统和导弹所在的位置如下图所示。要拦截所有导弹,在满足最小使用代价的前提下,两套系统工作半径的平方分别为2020 和1010。

【数据范围】

对于10\%10%的数据,N = 1N=1

对于20\%20%的数据,1 ≤ N ≤ 21≤N≤2

对于40\%40%的数据,1 ≤ N ≤ 1001≤N≤100

对于70\%70%的数据,1 ≤ N ≤ 10001≤N≤1000

对于100\%100%的数据,1 ≤ N ≤ 1000001≤N≤100000,且所有坐标分量的绝对值都不超过10001000。

NOIP 2010 普及组 第三题

代码:

#include<iostream>
#include<algorithm>
using namespace std;const int M = 100006, inf = 10000000;struct T{int x;int y;int a;int b;
}t[M];
int x_1, y_1, x_2, y_2;
int n;int cmp(T a, T b){return a.a>b.a;
}int main(){cin>>x_1>>y_1>>x_2>>y_2;cin>>n;for(int i = 1; i<=n; i++){cin>>t[i].x;cin>>t[i].y;t[i].a = (t[i].x - x_1)*(t[i].x-x_1) + (t[i].y-y_1)*(t[i].y-y_1);t[i].b = (t[i].x - x_2)*(t[i].x-x_2) + (t[i].y-y_2)*(t[i].y-y_2);}sort(t+1, t+n+1, cmp);int r2 = 0, ans = inf;for(int i = 1; i<=n; i++){r2 = max(t[i-1].b, r2);ans = min(ans,t[i].a+r2);}cout<<ans<<endl;return 0;
}

 


http://www.ppmy.cn/news/988414.html

相关文章

大致了解Redis

为了保证数据的可靠性&#xff0c;Redis 需要在磁盘上读写 AOF 和 RDB&#xff0c;但在高并发场景里&#xff0c;这就会直接带来两个新问题&#xff1a;一个是写 AOF 和RDB 会造成 Redis 性能抖动&#xff0c;另一个是 Redis 集群数据同步和实例恢复时&#xff0c;读 RDB 比较慢…

算法与数据结构(四)--排序算法

一.冒泡排序 原理图&#xff1a; 实现代码&#xff1a; /* 冒泡排序或者是沉底排序 *//* int arr[]: 排序目标数组,这里元素类型以整型为例; int len: 元素个数 */ void bubbleSort (elemType arr[], int len) {//为什么外循环小于len-1次&#xff1f;//考虑临界情况&#xf…

C++运算符重载介绍

C运算符重载介绍 运算符重载&#xff08;Operator Overloading&#xff09;本质上是一种语法特性&#xff0c;它允许用户自定义类对象在使用运算符时的行为。虽然运算符重载可以使得类对象的操作更加直观和灵活&#xff0c;但它与多态性的概念并没有直接关联。 在C中&#xff…

15.Netty源码之EventLoop

highlight: arduino-light Netty配置主从Reactor模式 通过将NioServerSocketChannel绑定到了bossGroup。 将NioServerSocketChannel接收到请求创建的SocketChannel放入workerGroup。 将2个不同的SocketChannel绑定到2个不同的Group完成了主从 Reactor 模式。 分配NIOEventLoop的…

推荐带500创作模型的付费创作V2.1.0独立版系统源码

ChatGPT 付费创作系统 V2.1.0 提供最新的对应版本小程序端&#xff0c;上一版本增加了 PC 端绘画功能&#xff0c; 绘画功能采用其他绘画接口 – 意间 AI&#xff0c;本版新增了百度文心一言接口。 后台一些小细节的优化及一些小 BUG 的处理&#xff0c;前端进行了些小细节优…

CAN转EtherNet/IP网关can协议破解服务

JM-EIP-CAN 是自主研发的一款 ETHERNET/IP 从站功能的通讯网关。该产品主要功能是将各种 CAN 总线和 ETHERNET/IP 网络连接起来。 本网关连接到 ETHERNET/IP 总线中做为从站使用&#xff0c;连接到 CAN 总线中根据节点号进行读写。 技术参数 ETHERNET/IP 技术参数 网关做为 …

Dendrogram | 今天是人见人爱、花见花开的环形Dendrogram!~(附完整代码)

1写在前面 好长时间没更新了&#xff0c;这周真的是天天都在手术室度过&#xff0c;常讲到的一句话就是苦的一比啊。&#x1fae0; 很久没有见过外面的世界了&#xff0c;世界那么大&#xff0c;我也想去看看&#xff01;~&#x1f602; 废话太多了&#xff0c;今天的教程是环形…

linux学习(gbd进程)[5]

gdb set var i n #可设置变量值进程 冯诺依曼结构

动态规划 回文子串

647. 回文子串 双指针法&#xff1a; 遍历回文中心---->一个回文中心---->两个回文中心 class Solution { public:int countSubstrings(string s) {int result0;for(int i0; i<s.size(); i){result count(s, i, i);result count(s, i, i1);}return result;}int co…

C++-Rust-一次性掌握两门语言

C-Rust-一次性掌握两门语言 简介特色数据类型声明常量、变量判断与循环函数抽象化的对象&#xff1a;类与接口枚举模板与泛型Lambda匿名函数表达式 简介 本文主要是通过介绍C和Rust的基础语法达成极速入门两门开发语言。 C是在C语言的基础之上添加了面向对象的类、重载、模板等…

Qt中线程的使用

Qt中线程的使用 在qt中线程的使用有两种方式&#xff0c;第一种就是创建一个类继承QObject类&#xff0c;之后使用moveToThread函数将线程添加到类中。另一种就是创建一个类继承QThread类&#xff0c;在类中实现run函数。 第一种方式&#xff1a; 1、首先创建一个自定义的类…

QTday4(鼠标事件和键盘事件/QT实现连接TCP协议)

笔记 #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QDebug> #include <QTcpServer>//服务器类 #include <QTcpSocket>//客户端类 #include <QMessageBox> #include <QList>//链表容器QT_BEGIN_NAMESPACE namespace Ui …

【JAVASE】顺序和选择结构

⭐ 作者&#xff1a;小胡_不糊涂 &#x1f331; 作者主页&#xff1a;小胡_不糊涂的个人主页 &#x1f4c0; 收录专栏&#xff1a;浅谈Java &#x1f496; 持续更文&#xff0c;关注博主少走弯路&#xff0c;谢谢大家支持 &#x1f496; 顺序和选择 1. 顺序结构2. 分支结构2.1 …

【手撕】priority_queue

系列文章目录 文章目录 系列文章目录前言 前言 模拟实现priority_queue。 #pragma once #include <vector> #include <iostream> #include <deque>using namespace std;namespace yyf {template<class T>struct less//大堆{bool operator()(const T&a…

如何在go中实现程序的优雅退出,go-kratos源码解析

使用kratos这个框架有近一年了&#xff0c;最近了解了一下kratos关于程序优雅退出的具体实现。 这部分逻辑在app.go文件中&#xff0c;在main中&#xff0c;找到app.Run方法&#xff0c;点进入就可以了 它包含以下几个部分: App结构体:包含应用程序的配置选项和运行时状态。 …

Java的第十六篇文章——枚举、反射和注解(后期再学一遍)

目录 1. 枚举 1.1 学习目标 1.2 内容讲解 1.2.1 枚举的概述 1.2.2 为什么要使用枚举 1.2.3 作用 1.2.4 格式 2. 反射 2.1 学习目标 2.2 内容讲解 2.2.1 类加载&#xff08;了解&#xff09; 2.2.2 类的加载过程 2.2.3 类的初始化 2.2.4 类的加载器 2.2.5 Java系…

UE4/5C++多线程插件制作(十八、Graph线程封装,以及宏的设置)

目录​​​​​​​ 什么是Graph线程? MTPThreadGraphManage.h MTPThreadInterface.h MTPThreadGraphManage.h MTPManage.cpp void FMTPThreadGraphManage::Wait(const FGraphEventRef& EventRef)</

【Ajax】笔记-同源策略

同源策略(Same-Origin Policy)&#xff0c;是浏览器的一种安全策略 同源&#xff08;即url相同&#xff09;&#xff1a;协议、域名、端口号 必须完全相同。&#xff08;请求是来自同一个服务&#xff09; 跨域&#xff1a;违背了同源策略&#xff0c;即跨域。 ajax请求是遵循…

[containerd] 在Windows上使用IDEA远程调试containerd, ctr, containerd-shim

文章目录 1. containerd安装2. 源码编译3. 验证编译的二进制文件是否含有调试需要的信息3.1. objdump工具验证3.2. file工具验证3.3. dlv工具验证 4. debug 1. containerd安装 [Ubuntu 22.04] 安装containerd 2. 源码编译 主要步骤如下&#xff1a; 1、从github下载containe…

P318javascript:void(‘FE2C24‘)3 [HAOI2016] 食物链(记忆化搜索)

1:思路&#xff1a; 从入读为零的点进行记忆化搜索&#xff0c;搜到出度为零的点返回1&#xff0c;所有返回值加起来就是答案。 int dfs(int u){if(f[u]!-1) return f[u];//记忆化搜索 int res0;if(chu[u]0) return 1;//到达食物链底端 for(auto to:v[u]){resdfs(to);}f[u]re…