感谢@JCarlson 翻译

题意:二维平面上有若干个点，选择其中一部分点，要求两两之间距离不超过d。

n<=100

很果断建个图,求最大团

用省选随机法很快就过掉了..

一遍过..

谈谈省选随机法是个什么东西

这玩意儿是我在省选现成的时候瞎搞用的..期望得分10分实际得分100分的东西..不然我就进不了省队了..

后来仔细思考了下,确实是个不错的算法,正确性似乎挺高

1,每次随机找一个点

2,随机找出一个和当前所有选的点都相邻的点

3,把它加入我们的团里面,如果此时还可以继续扩展,再执行2号操作

这样的话,我们随机多次就有很大的正确性

这题我设置的随机边界是5000000,但是其实可能还能再大点

具体的随机边界根据评测机调整即可

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
bool a[128][128];
int best_sol[128];
int max_ans=0;
int cnt;
const int TLE=5000000;
int n,d;
void dfs(int x)
{
    static int t[105];
    static int chosen[105];
    int i;
    for (i=0;i<n;i++)
    {
        t[i]=a[x][i];
        chosen[i]=false;
    }
    chosen[x]=true;
    int now_ans=1;
    cnt+=n;
    for (;;)
    {
        static int que[105];
        int prob_sol=0;
        for (i=0;i<n;i++)
        {
            if ((t[i])&&(!chosen[i]))
            {
                que[prob_sol++]=i;
            }
        }
        if (prob_sol+now_ans<=max_ans) return;
        if (prob_sol==0)
        {
            max_ans=now_ans;
            for (i=0;i<n;i++)
            {
                best_sol[i]=chosen[i];
            }
            return;
        }
        cnt+=n;
        int k=que[rand()%prob_sol];
        chosen[k]=true;
        for (i=0;i<n;i++)
        {
            t[i]&=a[k][i];
        }
        now_ans++;
        cnt+=n;
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    for (;scanf("%d%d",&n,&d)!=-1;)
    {
        static int x[105],y[105];
        int i;
        for (i=0;i<n;i++)
        {
            scanf("%d%d",&x[i],&y[i]);
        }
        for (i=0;i<n;i++)
        {
            int j;
            for (j=0;j<n;j++)
            {
                if ((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=d*d) a[i][j]=true; else a[i][j]=false;
            }
        }
        cnt=0;
        max_ans=0;
        for (;;)
        {
            dfs(rand()%n);
            if (cnt>=TLE) break;
        }
        printf("%d\n",max_ans);
        for (i=0;i<n;i++)
        {
            if (best_sol[i]) printf("%d ",i+1);
        }
        printf("\n");
    }
    return 0;
}