首页 > 其他 > 详细

P1158 导弹拦截

时间:2019-02-12 10:38:05      阅读:197      评论:0      收藏:0      [点我收藏+]

P1158 导弹拦截

思路

按每个点到第一个系统的距离排序,然后预处理出每个点及其之后的点到第二个系统的距离的最大值,再循环一遍枚举答案。

 代码

技术分享图片
 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cctype>
 6 using namespace std;
 7 
 8 #define res register int
 9 inline int read()
10 {
11     int x(0),f(1); char ch;
12     while(!isdigit(ch=getchar())) if(ch==-) f=-1;
13     while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-0,ch=getchar();
14     return f*x;
15 }
16 typedef long long LL;
17 const int N=100000+10;
18 int n,x1,y1,x2,y2;
19 int d[N];
20 struct node{
21     int x,y,z;
22 }s[N];
23 inline int calc(int a1,int b1,int a2,int b2)
24 {
25     return (a1-a2)*(a1-a2)+(b1-b2)*(b1-b2);
26 }
27 bool cmp(node a,node b) {return a.z<b.z;}
28 int main()
29 {
30     x1=read(); y1=read(); x2=read(); y2=read(); n=read();
31     for(res i=1 ; i<=n ; i++)
32     {
33         s[i].x=read(); s[i].y=read(); 
34         s[i].z=calc(x1,y1,s[i].x,s[i].y);    
35     }
36     sort(s+1,s+n+1,cmp);
37     for(res i=n ; i>=1 ; i--)
38         d[i]=max(d[i+1],calc(x2,y2,s[i].x,s[i].y)); 
39     int ans(d[1]);
40     for(res i=1 ; i<=n ; i++)
41     {
42         int tmp(s[i].z); tmp+=d[i+1];
43         ans=min(ans,tmp);
44     }
45     printf("%d\n",ans);
46     return 0;
47 }
View Code

 

P1158 导弹拦截

原文:https://www.cnblogs.com/wmq12138/p/10363882.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!