Codeforces 958E3 Guard Duty (hard)

题面在这里

考虑到黑点与白点个数相同就一定有解

那么可以分治做:找到一条连线把所有点分为两部分,使其黑白点个数相同

具体的做法就是,以最左下的点为原点极角排序,然后大力枚举分割点集的连线

如何证明一定能找到?

考虑遇到黑点+1,白点-1,那么初始是0,最终也是0,而且中间经过了\(2N-1\)个点

那么其中必定有零点,这就意味着找到了解

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<cstring>
#include<algorithm>
#define cl(x,y) memset(x,y,sizeof(x))
using namespace std;

const int maxn=20005;
int n,ans[maxn];
bool vis[maxn];
struct point{
int x,y,id;
bool f;
point() {}
point(int _x,int _y):x(_x),y(_y) {}
bool operator<(const point&b)const{
return x<b.x||x==b.x&&y<b.y;
}
}a[maxn],b[maxn],p;
typedef point vec;
inline vec operator-(const vec&a,const vec&b){
return vec(a.x-b.x,a.y-b.y);
}
inline int cross(const vec&a,const vec&b){
return a.x*b.y-a.y*b.x;
}
bool cmp(const point&a,const point&b){
return cross(a-p,b-p)>0;
}
void divide(int l,int r){
if (l>=r) return;
for (int i=l;i<=r;i++) b[i]=a[i];
swap(*min_element(a+l,a+r+1),a[r]);
p=a[r];
sort(a+l,a+r,cmp); cl(vis,0);
int i,j,t,mid;
for (i=l,t=0;i<r;vis[i]=1,t+=a[i].f?1:-1,i++)
if ((p.f^a[i].f)&&t==0) break;
mid=i;
if (!p.f) ans[p.id]=a[i].id;else ans[a[i].id]=p.id;
divide(l,mid-1);divide(mid+1,r-1);
for (int i=l;i<=r;i++) a[i]=b[i];
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y),a[i].id=i,a[i].f=0;
for (int i=n+1;i<=n+n;i++) scanf("%d%d",&a[i].x,&a[i].y),a[i].id=i,a[i].f=1;
divide(1,2*n);
for (int i=1;i<=n;i++) printf("%d\n",ans[i]-n);
return 0;
}