CodeForces 617C【序枚举】

时间:2023-03-08 18:23:41

题意:

有两个点喷水,有很多个点有花,给出坐标。

求使得每个花都可以被喷到,两个喷水的半径的平方的和最小是多少。

思路:

枚举其中一个喷水的最大半径。

坑:

这题我贪心的思路有很大问题。一开始也是想这样枚举的,但是思路超级混乱,按照r2进行贪心但是最后想想想法很荒谬。

顺序和题意一定要搞的很透彻才可以==

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct st
{
long long x,y,dis1,dis2;
};
bool cmp(st a,st b)
{
return a.dis1>b.dis1;
}
st point[];
st fla1,fla2;
long long cal(st a,st b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int main()
{
int n;
scanf("%d",&n);
long long r1=,r2=;
scanf("%I64d%I64d%I64d%I64d",&fla1.x,&fla1.y,&fla2.x,&fla2.y);
for(int i=;i<n;i++)
{
scanf("%I64d%I64d",&point[i].x,&point[i].y);
point[i].dis1=cal(point[i],fla1);
point[i].dis2=cal(point[i],fla2);
}
sort(point,point+n,cmp);
long long ans=point[].dis1;
r2=;
for(int i=;i<n;i++)
{
ans=min(ans,point[i].dis1+r2);
r2=max(r2,point[i].dis2);
}
ans=min(ans,r2);
printf("%I64d\n",ans);
}