[TIOJ 1631][IOI 2006] 點連接遊戲

這題我想了好久都沒頭緒，原本一直在想先隨便取一個生成樹再一直換，可是一直爛掉，最後是看解才會的，這解太神了QQ......

作法：

用 Divide and Conquer !!!!

首先把整個大正方形沿對角線切開，變成兩個直角三角形，那麼問題就變成我們要在一個凸包是三角形的點集上讓紅、綠點連通且線段兩兩不相交，並且凸包上有兩種顏色的點。以下記凸包上的點分別是A , B , C ，且 B和 C 同色( 和A不同色 )。首先如果凸包內沒有點那就作完了。如果凸包中的所有點顏色都一樣，那就直接全部連凸包上的和他同色的點就好了。否則那麼任取點集中的一個顏色和 A 一樣的點 P，把他和 A 相連，並且把整個三角形分成 PAB , PBC , PAC 三個部分，這樣對這三個部分遞回下去處理就可以了。但實作上還需要思考一下，我是每次都傳目前剩餘點的 index 的 vector 進函式裡面( 用 reference 傳，不然他會再把整個 vector 複製一次 )，而 vector 們就先在全域開好，需要的時候再從裡面拿出來用。另外在任取一點 P 那邊，聽官方解說用隨機取的點可以讓複雜度變 O( nlogn ) ，所以就照做了@@

code :

#include<bits/stdc++.h>
#include"lib1631.h"
#define LL long long
using namespace std;
const int maxn=50000+10 ;
 
struct pt{int x,y,c ;};
 
pt operator + (const pt &a,const pt &b) { return (pt){a.x+b.x,a.y+b.y,0} ; }
pt operator - (const pt &a,const pt &b) { return (pt){a.x-b.x,a.y-b.y,0} ; }
LL cross(const pt &a,const pt &b) { return (LL)a.x*b.y-(LL)a.y*b.x ; }
 
bool in_triangle(const pt &p,const pt &a,const pt &b,const pt &c)
{
    if(cross(b-a,c-a)>0) return
        cross(b-a,p-a)>0 && cross(c-b,p-b)>0 && cross(a-c,p-c)>0 ;
    else return
        cross(c-a,p-a)>0 && cross(b-c,p-c)>0 && cross(a-b,p-b)>0 ;
}
 
int n,m ;
vector<int> vec[maxn*10] ;
int vcnt=0 ;
pt p[2*maxn] ;
 
int tmp[2*maxn],sz ;
void solve(int a,int b,int c,const vector<int> &v)
{
    if(v.empty()) return ;
    if(p[a].c==p[b].c) swap(a,c) ;
    else if(p[a].c==p[c].c) swap(a,b) ;
 
    sz=0 ;
    int val=0 ;
    for(auto i : v)
    {
        val |= (p[i].c+1) ;
        if(p[i].c==p[a].c) tmp[sz++]=i ;
    }
    if(val==(p[a].c+1))
    {
        if(p[a].c==0) for(auto i : v) Report(0,a,i) ;
        else for(auto i : v) Report(1,a-n,i-n) ;
        return ;
    }
    else if(val==(p[b].c+1))
    {
        if(p[b].c==0) for(auto i : v) Report(0,b,i) ;
        else for(auto i : v) Report(1,b-n,i-n) ;
        return ;
    }
 
    int t=rand()%sz ;
    if(p[a].c==0) Report(0,a,tmp[t]) ;
    else Report(1,a-n,tmp[t]-n) ;
 
    int np=tmp[t] ;
    for(auto i : v) if(i!=np)
    {
        if(in_triangle(p[i],p[a],p[b],p[np])) vec[vcnt+1].push_back(i) ;
        else if(in_triangle(p[i],p[b],p[c],p[np])) vec[vcnt+2].push_back(i) ;
        else vec[vcnt+3].push_back(i) ;
    }
    int vval=vcnt ; vcnt+=3 ;
    solve(a,b,np,vec[vval+1]) ;
    solve(b,c,np,vec[vval+2]) ;
    solve(a,c,np,vec[vval+3]) ;
}
 
main()
{
    srand(time(NULL)) ;
    Init(n,m) ;
    for(int i=1;i<=n;i++) Get(0,p[i].x,p[i].y) , p[i].c=0 ;
    for(int i=n+1;i<=n+m;i++) Get(1,p[i].x,p[i].y) , p[i].c=1 ;
    for(int i=3;i<=n+m;i=(i==n?i+3:i+1))
    {
        if( p[i].x < p[1].y-p[i].y ) vec[0].push_back(i) ;
        else vec[1].push_back(i) ;
    }
    Report(0,1,2) ;
    Report(1,1,2) ;
    vcnt=1 ;
    solve(1,n+1,n+2,vec[0]) ;
    solve(1,2,n+2,vec[1]) ;
    Finish() ;
}