题解 UVA1411 【Ants】

2020-12-11 15:14:51


题意:给定平面中 $n$ 个黑点,$n$ 个白点,且不存在任意三点共线。一个黑点一个白点凑成一对,得到 $n$ 对点。每对点连一条线,要求没有线段相交。

方法:分治。

将纵坐标最小的点挑出来,如果满足条件的有多个,任选一个即可,这样剩下的点没有在这个点下面的。不妨设这个点为黑点,命名为点 $A$。

按照与 $A$ 的极角的顺序一个一个遍历剩下的点,并尝试把它和 $A$ 连线。如果遍历到一个白点,且之前遍历过的黑白点个数相等,那么连线成功。

这时候,发现遍历过的点和没有遍历过的点被这条线段所确定的直线分为两半,且两侧都能保证黑点白点个数相同。那么,将这两组点分别配对连线,可以保证不会有线段穿过那条分界的直线。所以,直线两侧分成两个子问题继续求解。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=114;
int n;
struct pnt{
    int x,y,col,idx;//col==0: colony; col==1:apple trees; idx表示下标;
    bool operator <(const pnt &a)const{
        return y<a.y;
    }
};
pnt operator -(const pnt &a,const pnt &b){
    return pnt{a.x-b.x,a.y-b.y,a.col,a.idx};
}
void rd(pnt &a,int col,int idx){//read
    scanf("%d%d",&a.x,&a.y);
    a.col=col,a.idx=idx;
}
bool cmp(const pnt &a,const pnt &b){
    return atan2(a.x,a.y)>=atan2(b.x,b.y);
}
pnt cor[maxn<<1];//保存所有点
int ans[maxn];//保存连线方案
void solve(int l,int r)//区间左闭右开
{
    if(l>=r)return;
    sort(cor+l,cor+r);//按照y排序
    rep(i,l+1,r-1)cor[i]=cor[i]-cor[l];
    sort(cor+l+1,cor+r,cmp);//极角排序
    int cnt=0;//用来判断黑白点个数是否相等,每遇到一个点,根据颜色选择+1或者-1
    rep(i,l+1,r-1)
    {
        if(cnt==0&&(cor[l].col^cor[i].col))//连线成功
        {
            cor[l].col?ans[cor[i].idx]=cor[l].idx:ans[cor[l].idx]=cor[i].idx;
            solve(l+1,i),solve(i+1,r);
            return;
        }
        cnt+=(cor[i].col?-1:1);
    }
}
int main()
{
    while(scanf("%d",&n)==1)
    {
        rep(i,1,(n<<1))//读取n*2个点
            rd(cor[i],((i-1)/n)?1:0,(i-1)%n+1);
        solve(1,(n<<1)|1);
        rep(i,1,n)
            printf("%d\n",ans[i]);
        puts("");
    }
    return 0;
}