codeforces 958E3

題意：

給出n個A類點和n個B類點，AB配對，要求連線不能有交點，輸出方案。

題解：

感覺是個比對，想不到解法，學習了别人的代碼，原來是分治，長知識了。。。

分治的思想是确定一個配對後，然後去解決确定配對的左邊和右邊。

那麼如何保證兩邊一定有解呢？方法比較巧妙。

假設目前處理的區間為

，我們先在區間内找到最下、最左的點，然後将這個區間内的其他點按極角排序，找出一個合法比對。

代碼：

#include<bits/stdc++.h>
#define N 100010
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define cl clear
#define si size
#define lb lowwer_bound
#define eps 1e-8
const LL P=1e9+7;
#define IO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define P 1000000007;
using namespace std;

struct Po
{
    int x,y,w,id;
}a[N],t;
int ans[N],t1,t2;

bool cmp(Po a,Po b)
{
    return a.y!=b.y?a.y<b.y:a.x<b.x;
}

bool cmp1(Po a,Po b)
{
    return (a.x-t.x)*(b.y-t.y)-(a.y-t.y)*(b.x-t.x)<0;
}

void work(int l,int r)
{
    if (l>r) return;
    int c=min_element(a+l,a+r+1,cmp)-a;
    swap(a[c],a[l]);
    t=a[l];
    sort(a+l+1,a+r+1,cmp1);
    t1=t2=0; int k;
    for (k=r;!(t.w!=a[k].w && t1==t2);k--)
        if (a[k].w==t.w) t1++;else t2++;

    if (t.w) ans[a[k].id]=t.id;
        else ans[t.id]=a[k].id;
    work(l+1,k-1);
    work(k+1,r);
}


int main()
{
    IO
    int n;
    cin>>n;
    for (int i=1;i<=n*2;i++)
    {
        cin>>a[i].x>>a[i].y;
        a[i].w=(i>n); a[i].id=i>n?i-n:i;
    }
    work(1,n*2);
    for (int i=1;i<=n;i++) cout<<ans[i]<<endl;
}