F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 2429 >> 这题二分+宽搜为毛过不了
AKCqhzdy @ 2017-11-25 14:18:08
[ Quote ] [ Edit ] [ Delete ] 1#
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;

struct tree
{
int x,y;
}t[1100];int m;
int n,a[510];

bool v[1100];
int list[1100];
int dis(tree n1,tree n2)
{
return (n1.x-n2.x)*(n1.x-n2.x)+(n1.y-n2.y)*(n1.y-n2.y);
}
bool check(int k)
{
memset(v,false,sizeof(v));v[1]=true;
int head=1,tail=2,rea=1;list[1]=1;
while(head!=tail)
{
tree tno=t[list[head]];
for(int i=1;i<=m;i++)
{
if(v[i]==false&&dis(tno,t[i])<=a[k]*a[k])
{
v[i]=true;
rea++;
list[tail]=i;
tail++;
}
}
head++;
}
if(rea==m)return true;
else return false;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);

scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d%d",&t[i].x,&t[i].y);

int l=1,r=n,ans;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid)==true)
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%d\n",n-ans+1);
return 0;
}
200815147 @ 2017-11-25 21:09:12
[ Quote ] [ Edit ] [ Delete ] 2#
裸的最小生成树啊,草哥
fengyecong @ 2017-11-27 13:30:01
[ Quote ] [ Edit ] [ Delete ] 3#
裸的最小生成树啊,草哥(%%%队长)
[Top] [Previous Page] [Next Page]

HOME Back