poj 1228 稳定凸包

时间:2022-09-14 10:48:59
Grandpa's Estate
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 12337   Accepted: 3451

Description

Being the only living descendant of his grandfather, Kamran the Believer inherited all of the grandpa's belongings. The most valuable one was a piece of convex polygon shaped farm in the grandpa's birth village. The farm was originally separated from the neighboring farms by a thick rope hooked to some spikes (big nails) placed on the boundary of the polygon. But, when Kamran went to visit his farm, he noticed that the rope and some spikes are missing. Your task is to write a program to help Kamran decide whether the boundary of his farm can be exactly determined only by the remaining spikes.

Input

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains an integer n (1 <= n <= 1000) which is the number of remaining spikes. Next, there are n lines, one line per spike, each containing a pair of integers which are x and y coordinates of the spike.

Output

There should be one output line per test case containing YES or NO depending on whether the boundary of the farm can be uniquely determined from the input.

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 稳定凸包的更多相关文章

  1. Grandpa&&num;39&semi;s Estate - POJ 1228&lpar;稳定凸包&rpar;

    刚开始看这个题目不知道是什么东东,后面看了大神的题解才知道是稳定凸包问题,什么是稳定凸包呢?所谓稳定就是判断能不能在原有凸包上加点,得到一个更大的凸包,并且这个凸包包含原有凸包上的所有点.知道了这个东 ...

  2. POJ 1228 &lpar;稳定凸包问题&rpar;

    <题目链接> <转载于  >>> > 首先来了解什么是稳定的凸包.比如有4个点: 这四个点是某个凸包上的部分点,他们连起来后确实还是一个凸包.但是原始的凸包可 ...

  3. POJ 1228 - Grandpa&&num;39&semi;s Estate 稳定凸包

    稳定凸包问题 要求每条边上至少有三个点,且对凸包上点数为1,2时要特判 巨坑无比,调了很长时间= = //POJ 1228 //稳定凸包问题,等价于每条边上至少有三个点,但对m = 1(点)和m = ...

  4. POJ 1228 Grandpa&&num;39&semi;s Estate 凸包 唯一性

    LINK 题意:给出一个点集,问能否够构成一个稳定凸包,即加入新点后仍然不变. 思路:对凸包的唯一性判断,对任意边判断是否存在三点及三点以上共线,如果有边不满足条件则NO,注意使用水平序,这样一来共线 ...

  5. 凸包稳定性判断:每条边上是否至少有三点 POJ 1228

    //凸包稳定性判断:每条边上是否至少有三点 // POJ 1228 #include <iostream> #include <cstdio> #include <cst ...

  6. POJ 1228&Tab; Grandpa&&num;39&semi;s Estate --深入理解凸包

    题意: 判断凸包是否稳定. 解法: 稳定凸包每条边上至少有三个点. 这题就在于求凸包的细节了,求凸包有两种算法: 1.基于水平序的Andrew算法 2.基于极角序的Graham算法 两种算法都有一个类 ...

  7. POJ 1228 Grandpa&&num;39&semi;s Estate&lpar;凸包&rpar;

    Grandpa's Estate Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 11289   Accepted: 3117 ...

  8. ●POJ 1228 Grandpas Estate

    题链: http://poj.org/problem?id=1228 题解: 计算几何,凸包 题意:给出一些点,求出其凸包,问是否是一个稳定的凸包. 稳定凸包:不能通过新加点使得原来凸包上的点(包括原 ...

  9. poj 3348 Cow 凸包面积

    Cows Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 8122   Accepted: 3674 Description ...

随机推荐

  1. 玩转Podfile

    前言 经常使用CocoaPods来管理iOS项目中的第三方库,但是我们要使用CocoaPods来管理第三方库,前提是要写好Podfile文件,通过这个文件来配置第三方库与项目之间的依赖.版本等信息. ...

  2. NGUI 屏幕自适应&lpar;初始设定宽高800x480只支持比其大的屏幕)

    自适应讲解部分可以参考以下网址:http://www.xuanyusong.com/archives/2536,下面代码中提到的AdaptiveManualHeight()函数就是参考该文章的. 下面 ...

  3. Asp&period;Net 高性能ORM框架 SqlSugar&period;ORM 2&period;8

    3.0最新API: http://www.cnblogs.com/sunkaixuan/p/5911334.html 1.前言/Preface SqlSugar从去年到现在已经一年了,版本从1.0升到 ...

  4. virtualbox虚拟机迁移出现&quot&semi;connot find device eth0&quot&semi;错误

    我在自己的机器上面配置virtualbox虚拟机完毕以后,移植到另外一台机器上面,登陆页面总是在检查network,并且最后网络加载失败,不论我是用桥接还是NAT方式连接.登陆系统以后,我尝试连接网络 ...

  5. Anddoi 将时间转换为指定时区的时间

    import java.text.Format;import java.text.ParseException;import java.text.SimpleDateFormat;import jav ...

  6. hdu 4925 贪心 自己从小到大做数据找方法规律

    http://acm.hdu.edu.cn/showproblem.php?pid=4925 自己逐个做数据找规律.提供下我的找的: 1 2 1 3 2 2 2 3 3 3 然后发现这种矩阵是最优的: ...

  7. java运行时数据区域

    数据区域有:程序计步器,虚拟机栈,本地方法栈,java堆,方法区 程序计步器: 它是一块较小的内存空间,它的作用可以看做是当先线程所执行的字节码的信号指示器. 每一条JVM线程都有自己的PC寄存器,各 ...

  8. 转:Jmeter以non-gui模式进行分布式测试

    由于Jmeter是一个纯JAVA的应用,用GUI模式运行压力测试时,对客户端的资源消耗是相当惊人的,所以在进行正式的压测时一定要使用non-gui模式运行,如果并发数很高或者客户端的硬件资源比较一般的 ...

  9. Python Django 之 MVT

    一.Django的MVT模式 M: Model, 模型 与MVC中的M相同,负责对数据的处理 V: View, 视图 与MVC中的C类似,负责处理用户请求,调用M和T,响应请求 T: Template ...

  10. JavaScript之DOM实践

    前言 HTML的DOM是JavaScript有能力对HTML作出反应,有时候,我们需要一些网页效果,为了更好地适应用户的效果,比如,我们平时接触,点击某个按钮,按下去的瞬间会变色,再比如,有时候鼠标经 ...