随机化乱搞
学习了一下bitset怎么用感觉不错
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<bitset>
#include<algorithm>
using namespace std;
const int N=105;
typedef bitset<N> Bt;
int n,d,ord[N],CNT=1000;
Bt A[N],nw,ans,can;
struct Point{
int x,y;
}poi[N];
int Sqr(int x){return x*x;}
int Dist(Point A,Point B){return Sqr(A.x-B.x)+Sqr(A.y-B.y);}
int main(){
freopen("4080.in","r",stdin);
freopen("4080.out","w",stdout);
scanf("%d %d",&n,&d);
for(int i=1;i<=n;i++)scanf("%d %d",&poi[i].x,&poi[i].y);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(Dist(poi[i],poi[j])<=d*d)A[i].set(j),A[j].set(i);
}
}
for(int i=1;i<=n;i++)ord[i]=i;
while(CNT--){
can.set();
nw.reset();
for(int i=1;i<=n;i++){
if(can.test(ord[i])){
nw.set(ord[i]);
can&=A[ord[i]];
}
}
if(nw.count()>ans.count())ans=nw;
random_shuffle(ord+1,ord+n+1);
}
printf("%d\n",ans.count());
for(int i=1;i<=n;i++)if(ans.test(i))printf("%d ",i);
return 0;
}
评论 (0)
