题解 P1158 【导弹拦截】

Humb1e · 2017-08-20 09:00:23 · 题解

贪心+快排

** 思路应该都明白，先把每个点到a，b两个点的距离求出来

然后从小到大排序，从最后一个开始枚举，相当于先把离a最远的归b管，其余归a管

并且不断地更新答案，最后输出即可。

但注意，ans的初值maxn应该大点（我先小了就没过）

下面代码：**

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 10000005   //可以适当大点 
using namespace std;
struct node
{
int x,y;
int s1,s2;
bool operator <(const node& b) const
{
return s1<b.s1;
}
}a[100005];
int main()
{
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
a[i].s1=(a[i].x-x1)*(a[i].x-x1)+(a[i].y-y1)*(a[i].y-y1);
        a[i].s2=(a[i].x-x2)*(a[i].x-x2)+(a[i].y-y2)*(a[i].y-y2);//算出距离 
}
sort(a+1,a+n+1);
int rb=0,ans=maxn;
for(int i=n;i;i--)
{
rb=max(rb,a[i+1].s2);
ans=min(ans,a[i].s1+rb);
}
printf("%d",ans);
return 0;
}