【随机化】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\n",ans);

    for(int i=1;i<ans;++i)

      printf("%d ",apa[i]);

    printf("%d\n",apa[ans]);

    return 0;

}