UVA1411 Ants
题意:
给定一些黑点白点,要求一个黑点连接一个白点,并且所有线段都不相交(保证不存在三点共线)
思路:
显然题目肯定有解。考虑到我们现在随便找将一个黑点与一个白点连边,这条线段所在的直线把整个点集分成了两部分,再分别对这两个点集分治进行相同操作。
具体细节:每次选出最左下的(x,y最小)的点,其他点(L到R区间)以这个点为中心进行极角排序。选择出黑点与白点相同的零界点(算上最左下的点),将这两个点连线。递归。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e2+5;
int n,ans[maxn];
struct node{
int x,y,id,col;
double ang;
}p[maxn];
bool cmp(node a,node b){
return a.ang<b.ang;
}
void dfs(int l,int r){
if(l>r)return;
int pos=l;
for(int i=l+1;i<=r;i++){
if(p[pos].y>p[i].y||p[pos].y==p[i].y&&p[pos].x>p[i].x)
pos=i;
}
swap(p[pos],p[l]);
int cnt=p[l].col;
for(int i=l+1;i<=r;i++)
p[i].ang=atan2(p[i].y-p[l].y,p[i].x-p[l].x);
sort(p+1+l,p+r+1,cmp);
for(int i=l+1;i<=r;i++){
cnt+=p[i].col;
if(cnt==0){
ans[p[l].id]=p[i].id;
ans[p[i].id]=p[l].id;
dfs(l+1,i-1);
dfs(i+1,r);
return;
}
}
}
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=2*n;i++){
scanf("%d%d",&p[i].x,&p[i].y);
p[i].id=i;
if(i<=n)p[i].col=1;
else p[i].col=-1;
}
dfs(1,n*2);
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]-n);
}
}