gym101221I Sensor Network
题意
给定 $n$ 个点，求最大点集使得点两两之间距离 $\leq d$。
题解
很容易将题意转化为 $x$ 选则 $y$ 不能选的限制，求最多选的点数。
那么就是一般图最小点覆盖。这个图显然不是二分图， 因为三个两两距离 $\gt d$ 的点很容易找到。
考虑枚举选出点集的直径。也就是枚举两个点，要求所有点间的距离都不超过这两个点的距离 $r$。
容易发现所有点都在以这两个点为圆心半径为 $r$ 的圆交的区域内。
把这样的点选出来，考虑前面的想法，也就是题意转化为 $x$ 选则 $y$ 不能选。此时容易发现在图形中不存在三个两两距离$\gt r$的点对。为啥？因为图形按照两个圆心连线分成两块，每一块的直径都不超过$r$，也就是不能在一块中选两个点，当然两块加起来就不能选 $3$ 个点了。
此时图形变成了个二分图(按照在连线哪边决定是黑还是白)，用dinic算最小点覆盖即可。
时间复杂度$O(n^{4.5})$。
代码
namespace flow{
const int N=105;
const int M=20005;
int to[M],lst[M],beg[N],w[M],e=1,cur[N],q[N],dis[M];
int n,s,t;
void init(){
for(int i=1;i<=n;++i){beg[i]=0;}
e=1;
}
void add(int u,int v,int c){
to[++e]=v;lst[e]=beg[u];beg[u]=e;w[e]=c;
to[++e]=u;lst[e]=beg[v];beg[v]=e;w[e]=0;
}
bool bfs(){
for(int i=1;i<=n;++i){cur[i]=beg[i];dis[i]=n+1;}
dis[s]=0;
int *l=q,*r=q;
*(l=r=q)=s;
while(l<=r){
for(int i=beg[*l];i;i=lst[i])if(w[i]&&chkmin(dis[to[i]],dis[*l]+1))*(++r)=to[i];
++l;
}
return dis[t]<n;
}
int dfs(int s,int t,int fl){
if(s==t)return fl;
for(int &i=cur[s];i;i=lst[i])if(w[i]&&dis[s]+1==dis[to[i]]){
int v=dfs(to[i],t,min(fl,w[i]));
if(v){w[i]-=v;w[i^1]+=v;return v;}
}
return 0;
}
int calc(){
int flow;
int ans=0;
while(bfs()){
while((flow=dfs(s,t,0x7fffffff)))ans+=flow;
}
return ans;
}
}
int n,w;
pii a[105];
int d[105][105];
vector<int> v1,v2;
int f(pii a,pii b,pii c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
signed main(){
#ifdef QAQAutoMaton
freopen("I.in","r",stdin);
freopen("I.out","w",stdout);
#endif
read(n,w);
w=sqr(w);
for(int i=1;i<=n;++i)read(a[i].x,a[i].y);
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)d[i][j]=sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y);
flow::n=n+2;
flow::s=n+1;flow::t=n+2;
int ans=1;
int wx,wy;
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j)if(d[i][j]<=w){
int l=d[i][j];
int c=2;
v1.clear();v2.clear();
flow::init();
for(int k=1;k<=n;++k)if(k!=i && k!=j && d[i][k]<=l&&d[j][k]<=l){
++c;
int lr=f(a[i],a[j],a[k]);
if(lr>0)v1.emplace_back(k);
else if(lr<0)v2.emplace_back(k);
}
for(auto x:v1)flow::add(n+1,x,1);
for(auto y:v2)flow::add(y,n+2,1);
for(int x:v1)for(int y:v2)if(d[x][y]>l)flow::add(x,y,inf);
if(chkmax(ans,c-flow::calc()))wx=i,wy=j;
}
}
write(ans,'\n');
if(ans==1)return write("1\n");
int i=wx,j=wy;
int l=d[i][j];
int c=2;
v1.clear();v2.clear();
flow::init();
write(i,' ',j);
for(int k=1;k<=n;++k)if(k!=i && k!=j && d[i][k]<=l&&d[j][k]<=l){
++c;
int lr=f(a[i],a[j],a[k]);
if(lr>0)v1.emplace_back(k);
else if(lr<0)v2.emplace_back(k);
else write(' ',k);
}
for(auto x:v1)flow::add(n+1,x,1);
for(auto y:v2)flow::add(y,n+2,1);
for(int x:v1)for(int y:v2)if(d[x][y]>l)flow::add(x,y,1);
flow::calc();
using flow::dis;
for(auto x:v1)if(dis[x]!=n+3)write(' ',x);
for(auto y:v2)if(dis[y]==n+3)write(' ',y);
putc('\n');
return 0;
}