分组赛时wy大神讲的题，网上都是随机化的题解
我来讲一下正解吧，我们穷举两个点，这两点距离要小于限制
然后我们分别以这两个点为圆心，两点距离为半径画圆
圆圆相交的部分被两点练成线段划分成两部分，不难发现
每个部分内点点之间的距离是小于限制的，很明显想到二分图
对于上半部分与下半部分的两点，如果距离大于限制则连边
然后我们求最大点独立集即可
求最大独立集的方案各种想错，实在太SB
做完最大匹配后首先先把未匹配的点拉出来，然后把他们有边相连的点都标记
然后处理每对匹配，若一个点被标记则选另一个点
这样是不可能出现两个点都标记的匹配，因为这样就会出现一条增广路，与最大匹配矛盾
type node=record
po,next:longint;
end; var e,ee:array[..] of node;
q,q1,q2,c,x,y,cy,cx,p:array[..] of longint;
v,v1,v2:array[..] 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<> do
begin
y:=e[i].po;
if not v[y] then
begin
v[y]:=true;
if (cy[y]=-) or (dfs(cy[y])=) then
begin
cy[y]:=x;
cx[x]:=y;
exit();
end;
end;
i:=e[i].next;
end;
exit();
end; function match:longint;
var i:longint;
begin
fillchar(cy,sizeof(cy),);
fillchar(cx,sizeof(cx),);
match:=t1+t2;
if (t2=) or (t1=) then exit;
for i:= to t1 do
if cx[i]=- 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:= to n do
readln(x[i],y[i]);
ans:=;
c[]:=;
for i:= to n- do
for j:=i+ to n do
if dis(i,j)<=d then
begin
ll:=dis(i,j);
t1:=;
t2:=;
fillchar(p,sizeof(p),);
fillchar(q,sizeof(q),);
len:=;
for k:= to n do
if (dis(i,k)<=ll) and (dis(j,k)<=ll) then
begin
if cross(k,j,i)>= then
begin
inc(t1);
q1[t1]:=k;
end
else begin
inc(t2);
q2[t2]:=k;
end;
end;
for k:= to t1 do
for l:= to t2 do
if dis(q1[k],q2[l])>d then add(k,l); l:=match;
if l>ans then
begin
ans:=;
fillchar(v1,sizeof(v1),false);
fillchar(v2,sizeof(v2),false);
for k:= to t1 do
if cx[k]=- then
begin
inc(ans);
c[ans]:=q1[k];
z:=p[k];
while z<> do
begin
v2[e[z].po]:=true;
z:=e[z].next;
end;
end; for k:= to t2 do
if cy[k]=- then
begin
inc(ans);
c[ans]:=q2[k];
z:=q[k];
while z<> do
begin
v1[ee[z].po]:=true;
z:=ee[z].next;
end;
end; for k:= to t1 do
if cx[k]<>- 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:= to ans do
write(c[i],' ');
writeln;
end.