平面上n个点,两个人交替决策,用线段连接两个点,但不能跨越其他点或者已经存在的线段。不能做的人算输,问你谁赢。

实际上,跟两个人的决策无关,n个点将平面三角剖分,只需要算出有几条边即可。

凸包上如果有K个点,那么图中那K-1条实边每条贡献一个三角形。

凸包内其他的边,每条贡献2个三角形。除了最中心那一个贡献一个。

假设总的三角形数是X,那么总的线段数就是(X*3+K)/2。

线段数是奇数就先手胜,否则后手胜。

#include<cstdio>
#include<algorithm>
using namespace std;
struct Point{
int x,y;
Point(const int &x,const int &y){
this->x=x;
this->y=y;
}
Point(){}
void read(){
scanf("%d%d",&x,&y);
}
}p[1005],q[1005];
typedef Point Vector;
Vector operator - (const Point &a,const Point &b){
return Vector(a.x-b.x,a.y-b.y);
}
int Cross(const Vector &a,const Vector &b){
return a.x*b.y-a.y*b.x;
}
bool cmp(const Point &a,const Point &b){
return a.x!=b.x ? a.x<b.x : a.y<b.y;
}
int n,K,T;
int main(){
// freopen("d.in","r",stdin);
scanf("%d",&T);
for(;T;--T){
K=0;
scanf("%d",&n);
for(int i=0;i<n;++i){
p[i].read();
}
sort(p,p+n,cmp);
bool flag=1;
for(int i=1;i<n-1;++i){
if(Cross(p[i+1]-p[i],p[i]-p[i-1])!=0){
flag=0;
break;
}
}
if(flag){
puts((n-1)%2==1 ? "T^T" : "OwO");
continue;
}
for(int i=0;i<n;++i){
while(K>1 && Cross(q[K-1]-q[K-2],p[i]-q[K-1])<0){
--K;
}
q[K++]=p[i];
}
for(int i=n-2,t=K;i>=0;--i){
while(K>t && Cross(q[K-1]-q[K-2],p[i]-q[K-1])<0){
--K;
}
q[K++]=p[i];
}
--K;
int A=K-1;
int B=n-K-1;
int sjxs=A+B*2+1;
puts((sjxs*3+K)/2%2==1 ? "T^T" : "OwO");
}
return 0;
}

最新文章

  1. Android自动化学习笔记之MonkeyRunner:官方介绍和简单实例
  2. [iOS 多线程 &amp; 网络 - 2.3] - 解析xml
  3. CentOS7 安装98五笔输入法
  4. 谈一下怎样设计Oracle 分区表
  5. Android NetWorkUtil
  6. editplus批量删除html代码空行
  7. iis无法加载样式
  8. Linux下添加自定义脚本到开机自启动,标准rpm,举例:设置Apache自启动
  9. MVC的HTTP请求处理过程(IIS应用程序池、CLR线程池)
  10. typescript handbook 学习笔记2
  11. 2. Mysql数据库的入门知识
  12. php 一个文件搞定支付宝支付,微信支付
  13. android 趟坑记
  14. location search的中文加密
  15. react创建项目报错unexpected end of json while parsing near xxx
  16. 归并排序算法-Java实现
  17. Java项目的结构
  18. fail-fast 与 fail-save 机制的区别
  19. Lucene.Net 优化索引生成,即搜索显示优化
  20. js 快速排序

热门文章

  1. 使用SQL Server连接xml接口,读取并解析数据
  2. Linux目录结构与文件权限——(五)
  3. C++之编译器与链接器工作原理
  4. 手動設定 電池溫度 mtk platform
  5. python实战===itchat
  6. linux===启动sdk manager下载配置sdk的时候报错的解决办法
  7. zip函数的应用
  8. 17:django Email
  9. python 结束练习
  10. ConcurrentHashMap的使用