分组赛时wy大神讲的题，网上都是随机化的题解

我来讲一下正解吧，我们穷举两个点，这两点距离要小于限制

然后我们分别以这两个点为圆心，两点距离为半径画圆

圆圆相交的部分被两点练成线段划分成两部分，不难发现

每个部分内点点之间的距离是小于限制的，很明显想到二分图

对于上半部分与下半部分的两点，如果距离大于限制则连边

然后我们求最大点独立集即可

求最大独立集的方案各种想错，实在太SB

做完最大匹配后首先先把未匹配的点拉出来，然后把他们有边相连的点都标记

然后处理每对匹配，若一个点被标记则选另一个点

这样是不可能出现两个点都标记的匹配，因为这样就会出现一条增广路，与最大匹配矛盾

type node=record       po,next:longint;     end;var e,ee:array[0..10010] of node;    q,q1,q2,c,x,y,cy,cx,p:array[0..110] of longint;    v,v1,v2:array[0..110] of boolean;    z,ll,d,t1,t2,i,j,k,l,ans,len,n:longint;procedure add(x,y:longint);  begin    inc(len);    e[len].po:=y;    e[len].next:=p[x];    p[x]:=len;    ee[len].po:=x;    ee[len].next:=q[y];    q[y]:=len;  end;function dfs(x:longint):longint;  var i,y:longint;  begin    i:=p[x];    while i<>0 do    begin      y:=e[i].po;      if not v[y] then      begin        v[y]:=true;        if (cy[y]=-1) or (dfs(cy[y])=1) then        begin          cy[y]:=x;          cx[x]:=y;          exit(1);        end;      end;      i:=e[i].next;    end;    exit(0);  end;function match:longint;  var i:longint;  begin    fillchar(cy,sizeof(cy),255);    fillchar(cx,sizeof(cx),255);    match:=t1+t2;    if (t2=0) or (t1=0) then exit;    for i:=1 to t1 do      if cx[i]=-1 then      begin        fillchar(v,sizeof(v),false);        match:=match-dfs(i);      end;  end;function cross(i,j,k:longint):longint;  begin    exit((x[i]-x[k])*(y[j]-y[k])-(x[j]-x[k])*(y[i]-y[k]));  end;function dis(i,j:longint):longint;  begin    exit(sqr(x[i]-x[j])+sqr(y[i]-y[j]));  end;begin  readln(n,d);  d:=d*d;  for i:=1 to n do    readln(x[i],y[i]);  ans:=1;  c[1]:=1;  for i:=1 to n-1 do    for j:=i+1 to n do      if dis(i,j)<=d then      begin        ll:=dis(i,j);        t1:=0;        t2:=0;        fillchar(p,sizeof(p),0);        fillchar(q,sizeof(q),0);        len:=0;        for k:=1 to n do          if (dis(i,k)<=ll) and (dis(j,k)<=ll) then          begin            if cross(k,j,i)>=0 then            begin              inc(t1);              q1[t1]:=k;            end            else begin              inc(t2);              q2[t2]:=k;            end;          end;        for k:=1 to t1 do          for l:=1 to t2 do            if dis(q1[k],q2[l])>d then add(k,l);        l:=match;        if l>ans then        begin          ans:=0;          fillchar(v1,sizeof(v1),false);          fillchar(v2,sizeof(v2),false);          for k:=1 to t1 do             if cx[k]=-1 then            begin              inc(ans);              c[ans]:=q1[k];              z:=p[k];              while z<>0 do              begin                v2[e[z].po]:=true;                z:=e[z].next;              end;            end;          for k:=1 to t2 do            if cy[k]=-1 then            begin              inc(ans);              c[ans]:=q2[k];              z:=q[k];              while z<>0 do              begin                v1[ee[z].po]:=true;                z:=ee[z].next;              end;            end;          for k:=1 to t1 do            if cx[k]<>-1 then            begin              inc(ans);              if not v1[k] then c[ans]:=q1[k]              else c[ans]:=q2[cx[k]];            end;        end;      end;  writeln(ans);  for i:=1 to ans do    write(c[i],' ');  writeln;end.