【Pre-Finals 2016, NTU Contest D】Drawing Hell 题解

题目大意

  平面上有 $n$ 个点，两人轮流博弈。每人每回合画一条线段连接两个点，不能在端点外的地方穿过已画的线段或其他端点。不能操作者输。问先手必胜或必败。

  $n,|x_i|,|y_i| \leq 1000$，可以三点共线，没有重点。
  多测，$T \leq 1000$
  2s

$$\\$$ $$\\$$ $$\\$$

题解

  从简单情况入手。如果给定的是一个凸包，且没有三点共线，那么最终局面就是三角划分，边数为 $2n-3$，这个一定是奇数，因此先手必胜。

  这启示我们用三角划分来考虑。

  对于一般情况：如果所有点共线，那么没有凸包也没有三角划分，边数就是 $n-1$，是奇数则先手胜。
  如果不是所有点共线，那么就有凸包，最终局面一定是三角划分，形成一个平面图。设最终边数为 $m$，平面上区域数为 $F$，凸包上的点数（含凸包边上的点）为 $c$，联立平面图欧拉定理和极大三角划分的边数关系得：

$$\begin{cases} n-m+F=2 \\ 3(F-1)=2(m-c)+c \\ \end{cases} \\$$

  解得 $m=3n-3-c=(2n-3)+(n-c)$，也就是说凸包内的点数的奇偶性决定了先手胜负。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=1005;

struct P{
	int x,y;
};
P operator - (const P &a,const P &b) {return (P){a.x-b.x,a.y-b.y};}
int operator * (const P &a,const P &b) {return a.x*b.y-a.y*b.x;}
bool cmpP(const P &a,const P &b) {return a.x<b.x || a.x==b.x && a.y<b.y;}

int n;
P p[maxn];

P h[2*maxn];
int h0;
bool fuck;
void Hell()
{
	sort(p+1,p+1+n,cmpP);
	h0=0;
	fo(i,1,n)
	{
		while (h0>=2 && (h[h0]-h[h0-1])*(p[i]-h[h0])>0) h0--;
		h[++h0]=p[i];
	}
	fd(i,n-1,1)
	{
		while (h0>=2 && (h[h0]-h[h0-1])*(p[i]-h[h0])>0) h0--;
		h[++h0]=p[i];
	}
	fuck=(h0==2*n-1);
	h0--;
}

int T;
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		fo(i,1,n) scanf("%d %d",&p[i].x,&p[i].y);
		
		Hell();
		
		bool ans=(fuck) ?((n-1)&1) :((n-h0+1)&1) ;
		puts(ans ?"T^T" :"OwO");
	}
}