Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 12337 | Accepted: 3451 |
Description
Input
Output
Sample Input
1
6
0 0
1 2
3 4
2 0
2 4
5 0
Sample Output
NO
/*
poj 1228 稳定凸包 给你n个节点构成一个凸包,问再添加节点是否能够形成新的凸包
比如: 这个点构成正方形可以看成一个不稳定凸包
___ ___
| | --> / |
|___| --> \___| 当一条边上有3个或者以上的点时,无论你怎么添加都无法改变的
当逆时针旋转的时候,凸包可以看成 每次只能左转或者直走构成的一个图形
当3个点一条线时,如果添加在凸包外面,那么它必需右转才可能经过那个点 所以我能需要求出凸包然后判断它们是否每条边上都有3个点即可
一个不错的图解:
http://www.cnblogs.com/xdruid/archive/2012/06/20/2555536.html
hhh-2016-05-07 22:17:34
*/
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#include <functional>
#include <map>
using namespace std;
#define lson (i<<1)
#define rson ((i<<1)|1)
typedef long long ll;
using namespace std;
const int maxn = 1010;
double PI = 3.1415926;
double eps = 1e-8; int sgn(double x)
{
if(fabs(x) < eps) return 0;
if(x < 0)
return -1;
else
return 1;
} struct Point
{
double x,y;
Point() {}
Point(double _x,double _y)
{
x = _x,y = _y;
}
Point operator -(const Point &b)const
{
return Point(x-b.x,y-b.y);
}
double operator ^(const Point &b)const
{
return x*b.y-y*b.x;
}
double operator *(const Point &b)const
{
return x*b.x + y*b.y;
}
}; struct Line
{
Point s,t;
Line() {}
Line(Point _s,Point _t)
{
s = _s;
t = _t;
}
pair<int,Point> operator &(const Line&b)const
{
Point res = s;
if( sgn((s-t) ^ (b.s-b.t)) == 0) //通过叉积判断
{
if( sgn((s-b.t) ^ (b.s-b.t)) == 0)
return make_pair(0,res);
else
return make_pair(1,res);
}
double ta = ((s-b.s)^(b.s-b.t))/((s-t)^(b.s-b.t));
res.x += (t.x-s.x)*ta;
res.y += (t.y-s.y)*ta;
return make_pair(2,res);
}
};
Point lis[maxn];
int Stack[maxn],top; double dist(Point a,Point b)
{
return sqrt((a-b)*(a-b));
}
bool cmp(Point a,Point b)
{
double t = (a-lis[0])^(b-lis[0]);
if(sgn(t) == 0)
{
return dist(a,lis[0]) <= dist(b,lis[0]);
}
if(sgn(t) < 0)
return false;
else
return true;
} bool Cross(Point a,Point b,Point c)
{
return (b.y-a.y)*(c.x-b.x) == (c.y-b.y)*(b.x-a.x);
} void Graham(int n)
{
Point p; int k = 0;
p = lis[0];
for(int i = 1; i < n; i++)
{
if(p.y > lis[i].y || (p.y == lis[i].y && p.x > lis[i].x))
p = lis[i],k = i;
}
swap(lis[0],lis[k]);
sort(lis+1,lis+n,cmp);
if(n == 1)
{
top = 1;
Stack[0] = 0;
return ;
}
if(n == 2)
{
Stack[0] = 0,Stack[1] = 1;
top = 2;
return;
}
Stack[0] = 0;
Stack[1] = 1;
top = 2;
for(int i = 2; i < n; i++)
{
while(top > 1 && sgn((lis[Stack[top-1]]-lis[Stack[top-2]])
^ (lis[i]-lis[Stack[top-2]])) < 0)
top --;
Stack[top++] = i;
}
} int main()
{
//freopen("in.txt","r",stdin);
int n,T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
scanf("%lf%lf",&lis[i].x,&lis[i].y);
}
if(n < 6)
{
printf("NO\n");
continue;
}
Graham(n);
int flag = 1;
for(int i = 1;i < top-1;i++)
{
if(Cross(lis[Stack[i-1]],lis[Stack[i]],lis[Stack[i+1]]) == 0
&& Cross(lis[Stack[i]],lis[Stack[i+1]],lis[Stack[i+2]]) == 0)
{
flag = 0;
break;
}
}
if(flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
poj 1228 稳定凸包的更多相关文章
-
Grandpa&#39;s Estate - POJ 1228(稳定凸包)
刚开始看这个题目不知道是什么东东,后面看了大神的题解才知道是稳定凸包问题,什么是稳定凸包呢?所谓稳定就是判断能不能在原有凸包上加点,得到一个更大的凸包,并且这个凸包包含原有凸包上的所有点.知道了这个东 ...
-
POJ 1228 (稳定凸包问题)
<题目链接> <转载于 >>> > 首先来了解什么是稳定的凸包.比如有4个点: 这四个点是某个凸包上的部分点,他们连起来后确实还是一个凸包.但是原始的凸包可 ...
-
POJ 1228 - Grandpa&#39;s Estate 稳定凸包
稳定凸包问题 要求每条边上至少有三个点,且对凸包上点数为1,2时要特判 巨坑无比,调了很长时间= = //POJ 1228 //稳定凸包问题,等价于每条边上至少有三个点,但对m = 1(点)和m = ...
-
POJ 1228 Grandpa&#39;s Estate 凸包 唯一性
LINK 题意:给出一个点集,问能否够构成一个稳定凸包,即加入新点后仍然不变. 思路:对凸包的唯一性判断,对任意边判断是否存在三点及三点以上共线,如果有边不满足条件则NO,注意使用水平序,这样一来共线 ...
-
凸包稳定性判断:每条边上是否至少有三点 POJ 1228
//凸包稳定性判断:每条边上是否至少有三点 // POJ 1228 #include <iostream> #include <cstdio> #include <cst ...
-
POJ 1228	 Grandpa&#39;s Estate --深入理解凸包
题意: 判断凸包是否稳定. 解法: 稳定凸包每条边上至少有三个点. 这题就在于求凸包的细节了,求凸包有两种算法: 1.基于水平序的Andrew算法 2.基于极角序的Graham算法 两种算法都有一个类 ...
-
POJ 1228 Grandpa&#39;s Estate(凸包)
Grandpa's Estate Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 11289 Accepted: 3117 ...
-
●POJ 1228 Grandpas Estate
题链: http://poj.org/problem?id=1228 题解: 计算几何,凸包 题意:给出一些点,求出其凸包,问是否是一个稳定的凸包. 稳定凸包:不能通过新加点使得原来凸包上的点(包括原 ...
-
poj 3348 Cow 凸包面积
Cows Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 8122 Accepted: 3674 Description ...
随机推荐
-
玩转Podfile
前言 经常使用CocoaPods来管理iOS项目中的第三方库,但是我们要使用CocoaPods来管理第三方库,前提是要写好Podfile文件,通过这个文件来配置第三方库与项目之间的依赖.版本等信息. ...
-
NGUI 屏幕自适应(初始设定宽高800x480只支持比其大的屏幕)
自适应讲解部分可以参考以下网址:http://www.xuanyusong.com/archives/2536,下面代码中提到的AdaptiveManualHeight()函数就是参考该文章的. 下面 ...
-
Asp.Net 高性能ORM框架 SqlSugar.ORM 2.8
3.0最新API: http://www.cnblogs.com/sunkaixuan/p/5911334.html 1.前言/Preface SqlSugar从去年到现在已经一年了,版本从1.0升到 ...
-
virtualbox虚拟机迁移出现";connot find device eth0";错误
我在自己的机器上面配置virtualbox虚拟机完毕以后,移植到另外一台机器上面,登陆页面总是在检查network,并且最后网络加载失败,不论我是用桥接还是NAT方式连接.登陆系统以后,我尝试连接网络 ...
-
Anddoi 将时间转换为指定时区的时间
import java.text.Format;import java.text.ParseException;import java.text.SimpleDateFormat;import jav ...
-
hdu 4925 贪心 自己从小到大做数据找方法规律
http://acm.hdu.edu.cn/showproblem.php?pid=4925 自己逐个做数据找规律.提供下我的找的: 1 2 1 3 2 2 2 3 3 3 然后发现这种矩阵是最优的: ...
-
java运行时数据区域
数据区域有:程序计步器,虚拟机栈,本地方法栈,java堆,方法区 程序计步器: 它是一块较小的内存空间,它的作用可以看做是当先线程所执行的字节码的信号指示器. 每一条JVM线程都有自己的PC寄存器,各 ...
-
转:Jmeter以non-gui模式进行分布式测试
由于Jmeter是一个纯JAVA的应用,用GUI模式运行压力测试时,对客户端的资源消耗是相当惊人的,所以在进行正式的压测时一定要使用non-gui模式运行,如果并发数很高或者客户端的硬件资源比较一般的 ...
-
Python Django 之 MVT
一.Django的MVT模式 M: Model, 模型 与MVC中的M相同,负责对数据的处理 V: View, 视图 与MVC中的C类似,负责处理用户请求,调用M和T,响应请求 T: Template ...
-
JavaScript之DOM实践
前言 HTML的DOM是JavaScript有能力对HTML作出反应,有时候,我们需要一些网页效果,为了更好地适应用户的效果,比如,我们平时接触,点击某个按钮,按下去的瞬间会变色,再比如,有时候鼠标经 ...