[文章目录]
Description
给定平面内的n个点，选出一个点集S，使得S里的所有点两两之间欧几里得距离不超过d，问|S|的最大值以及S里的点都有哪些。若答案有多种，输出任意一个。
第一行两个整数n和d，分别表示烤鸭店数和老板给魔法炮的路费。
题目特点：选了几个点之后，基本区域固定，点集趋于稳定。点具有空间的连续性。
以上是瞎说的，其实就是知道这题随机化能解强加的几个理由。
那么既然是随机化，我们就将点集随机排序，然后1~n进行n方暴力选点，能加就加。<algorithm>里有一个将序列随机的函数，random_shuffle(a+1,a+n+1): 对指定范围内的元素随机调整次序。感觉不错哦。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,d,ans;
struct node
{
int x,y,id;
}a[110];
bool v[110],fna[110];
int dis(int x,int y)
{
return (a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y);
}
int check()
{
memset(v,0,sizeof(v));
int i,j,num=1; v[1]=1;
for(i=2;i<=n;i++)
{
for(j=1;j<i;j++)
if(v[j]&&dis(i,j)>d*d) break;
if(j==i) v[i]=1,num++;
}
return num;
}
int main()
{
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++)
{
a[i].id=i;
scanf("%d%d",&a[i].x,&a[i].y);
}
int mx=1000000/n/n;
for(int i=1;i<=mx;i++)
{
random_shuffle(a+1,a+n+1);
int tmp=check();
if(tmp>ans)
{
ans=tmp;
for(int j=1;j<=n;j++) fna[a[j].id]=v[j];
}
}
printf("%d\n",ans);
for(int i=1;i<=n;i++)
if(fna[i]) {ans--;printf("%d%c",i,(ans==0)?'\n':' ');}
return 0;
}