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;
}