<题目链接>

<转载于  >>> >

首先来了解什么是稳定的凸包。比如有4个点:

这四个点是某个凸包上的部分点,他们连起来后确实还是一个凸包。但是原始的凸包可能不是这样。

比如:

即这四个点构成的凸包不算做“稳定”的。我们发现,当凸包上存在一条边上的点只有端点两个点的时候,这个凸包不是稳定的,因为它可以在这条边外再引入一个点,构成一个新的凸包。但一旦一条边上存在三个点,那么不可能再找到一个点使它扩展成一个新的凸包,否则构成的新多边形将是凹的。

下面是一个典型的稳定凸包:

于是此题的做法就很明确了,就是在给出的点中,找到凸包,并且判断这个凸包是不是每条边至少有三个点。

 #include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define eps 1e-8
using namespace std; struct point{
double x,y;
};
point p[],stack[];
int N,top;
double multi(point p1, point p2, point p3){ //向量(p1->p2)^(p1->p3)
return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
double dis(point a, point b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int cmp(const void *a, const void *b){ //按极角排序
point c = *(point *)a;
point d = *(point *)b;
double k = multi(p[], c, d);
if(k < || (!k && dis(c, p[]) > dis(d, p[]))) return ;
return -;
}
void Convex(){ //凸包的构建 Andrew算法
for(int i = ; i < N; i++){ //先按x,y坐标排序,找到原点
point temp;
if(p[i].y < p[].y || ( p[i].y == p[].y && p[i].x < p[].x)){
temp = p[i];
p[i] = p[];
p[] = temp;
}
}
qsort(p + , N - , sizeof(p[]), cmp); //再将除原点以外的点按极角排序
stack[] = p[]; //先将起始的两个点压入栈内,在进行后面的判断
stack[] = p[];
top = ;
for(int i = ; i < N; i++){
while(top >= && multi(stack[top - ], stack[top], p[i]) < )top--; //共线的点也压入凸包内;
top++;
stack[top] = p[i];
}
}
bool judge(){ //这个函数是关键
for(int i=;i<top;i++){
if((multi(stack[i-],stack[i+],stack[i]))!=&&(multi(stack[i],stack[i+],stack[i+]))!=) //判断每条边是否有至少三个点,即判断i-1,i,i+1这三个点是否在一条直线上或者i,i+1,i+2是否在一条直线上
return false;
}
return true;
}
int main(){
int t;
cin>>t;
while(t--){
cin>>N;
for(int i=;i<N;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
if(N<)puts("NO");
else{
Convex();
if(judge())puts("YES");
else puts("NO");
}
}
return ;
}

2018-08-23

最新文章

  1. MVC中权限管理
  2. 开篇----JavaScript细节的那些事儿
  3. drawing
  4. RecyclerView 介绍 02 – 重要概念
  5. 使用media Queries实现一个响应式的菜单
  6. [转载]C#.NET中Dns类的常用方法及说明
  7. 如何识别SQL Server中的IO瓶颈
  8. JBPM4.4 基本使用
  9. Mysql主从复制_模式之日志点复制
  10. [LeetCode] 4 Keys Keyboard 四键的键盘
  11. Python函数参数&amp;time、OS、json模块
  12. CAJ转换成PDF在线方法是什么
  13. fragment滑动界面
  14. JS中的&lt;a&gt;标签
  15. CSRF攻击详解
  16. Android.mk高级写法
  17. Codeforces 447D - DZY Loves Modification
  18. [SQLServer] 内存占用查看
  19. SD/MMC相关寄存器的介绍
  20. C++多线程编程一

热门文章

  1. JavaScript之字符串匹配工具[插件]
  2. k8s系列~docker mysql
  3. Handler实现与机制 &amp;&amp; Blocking Queue &amp;&amp; IdleHandler使用
  4. ROS Kinetic Install on Debian 9
  5. python 退出程序的方式
  6. windows环境变量PATH顺序的重要性
  7. 【转】void及void指针的深刻解析
  8. css实现左(右)侧固定宽度,右(左)侧宽度自适应 ---清除浮动
  9. cas中总是得不到返回的属性
  10. --save-dev和--save的区别