【随机化】bzoj4080 [Wf2014]Sensor Network

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double db;
struct Point{int x,y,p;}p[101],path[101];
int n,m,ans,apa[101];
int sqr(int x){return x*x;}
int dis(Point a,Point b){return sqr(a.x-b.x)+sqr(a.y-b.y);}
int e;
bool check(int x)
{
    for(int i=1;i<=e;++i)
      if(dis(p[x],path[i])>m*m)
        return 0;
    return 1;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
      {
        scanf("%d%d",&p[i].x,&p[i].y);
        p[i].p=i;
      }
    for(int i=1;i<=1000;++i)
      {
        random_shuffle(p+1,p+1+n);
        e=0;
        for(int j=1;j<=n;++j)
          if(check(j))
            path[++e]=p[j];
        if(e>ans)
          {
            ans=e;
            for(int j=1;j<=e;++j)
              apa[j]=path[j].p;
          }
      }
    printf("%d
",ans);
    for(int i=1;i<ans;++i)
      printf("%d ",apa[i]);
    printf("%d
",apa[ans]);
    return 0;
}