刚开始看这个题目不知道是什么东东,后面看了大神的题解才知道是稳定凸包问题,什么是稳定凸包呢?所谓稳定就是判断能不能在原有凸包上加点,得到一个更大的凸包,并且这个凸包包含原有凸包上的所有点。知道了这个东西就简单了,直接求出来凸包后,然后判断每条边上的点是否超过三点就行了。
代码如下:
============================================================================================================================
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std; const double EPS = 1e-;
const int MAXN = ;
const int oo = 1e9+; int sta[MAXN], top; struct point
{
double x, y; point(double x=, double y=):x(x), y(y){}
point operator - (const point &t)const{
return point(x-t.x, y-t.y);
}
double operator *(const point &t)const{
return x*t.x + y*t.y;
}
double operator ^(const point &t)const{
return x*t.y - y*t.x;
}
}p[MAXN];
int Sign(double t)
{
if(t > EPS)return ;
if(fabs(t) < EPS)return ;
return -;
}
double Dist(point a, point b)
{
return sqrt((a-b)*(a-b));
}
bool cmp(point a, point b)
{
int t = Sign((a-p[])^(b-p[])); if(t == )
return Dist(a, p[]) < Dist(b, p[]);
return t > ;
}
void Graham(int N)
{
int k=; for(int i=; i<N; i++)
{
if(p[k].y>p[i].y || (Sign(p[k].y-p[i].y)== && p[k].x > p[i].x))
k = i;
}
swap(p[], p[k]);
sort(p+, p+N, cmp); sta[]=, sta[]=, top=; if(N < )
{
top = N-;
return ;
} for(int i=; i<N; i++)
{
while(top> && Sign((p[i]-p[sta[top]])^(p[sta[top-]]-p[sta[top]])) <= )
top--;
sta[++top] = i;
}
} int main()
{
int T, N, i, j; scanf("%d", &T); while(T--)
{
scanf("%d", &N); for(i=; i<N; i++)
scanf("%lf%lf", &p[i].x, &p[i].y); Graham(N);
sta[++top] = sta[]; for(i=; i<top; i++)
{
int s=sta[i], e=sta[i+];
for(j=; j<N; j++)
{
if(j==s || j==e)
continue;
if(Sign( (p[s]-p[e])^(p[j]-p[e]) ) == )
break;
} if(j == N)
break;
} if(i < top || top < )
printf("NO\n");
else
printf("YES\n");
} return ;
}
Grandpa's Estate - POJ 1228(稳定凸包)的更多相关文章
-
poj 1228 稳定凸包
Grandpa's Estate Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 12337 Accepted: 3451 ...
-
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 Grandpa&#39;s Estate(凸包)
Grandpa's Estate Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 11289 Accepted: 3117 ...
-
POJ 1228	 Grandpa&#39;s Estate --深入理解凸包
题意: 判断凸包是否稳定. 解法: 稳定凸包每条边上至少有三个点. 这题就在于求凸包的细节了,求凸包有两种算法: 1.基于水平序的Andrew算法 2.基于极角序的Graham算法 两种算法都有一个类 ...
-
POJ1228 Grandpa&#39;s Estate 稳定凸包
POJ1228 转自http://www.cnblogs.com/xdruid/archive/2012/06/20/2555536.html 这道题算是很好的一道凸包的题吧,做完后会加深对凸包的 ...
-
●POJ 1228 Grandpas Estate
题链: http://poj.org/problem?id=1228 题解: 计算几何,凸包 题意:给出一些点,求出其凸包,问是否是一个稳定的凸包. 稳定凸包:不能通过新加点使得原来凸包上的点(包括原 ...
-
凸包稳定性判断:每条边上是否至少有三点 POJ 1228
//凸包稳定性判断:每条边上是否至少有三点 // POJ 1228 #include <iostream> #include <cstdio> #include <cst ...
随机推荐
-
C#和Javascript的try…catch…finally的一点差别
C#中规定:如果程序的控制流进入了一个带finally块的try语句,那么finally语句块始终会被执行 例子: class Program { static void Main(string[] ...
-
LaTex数学符号
http://web.ift.uib.no/Teori/KURS/WRK/TeX/symALL.html
-
android 二维码生成
1,activity public void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); set ...
-
Winform与WPF对话框(MessageBox, Dialog)之比较
Winform:使用System.Windows.Forms命名空间中相应控件; WPF则调用Microsoft.Win32. MessageBox: // WinForm private void ...
-
JavaScript总结之单击弹出div
今天也算用了不少手段来实现他们的要求,大概记录一下,下边的代码示例,我全部修改贴出来,争取全部占到自己的代码里就能用. 1.点击同一个div,打开/关闭另一个div. 1 <script typ ...
-
pureMVC简单示例及其原理讲解五(Facade)
本节将讲述Facade,Proxy.Mediator.Command的统一管家.自定义Facade必须继承Facade,在本示例中自定义Facade名称为ApplicationFacade,这个名称也 ...
-
unity加载ab后,场景shader不起效问题(物件表现黑色)
需要把unity自带的shader,加入到默认列表
-
[2019BUAA软件工程]结对编程感想
结对编程感想 写在前面 本博客为笔者在完成软件工程结对编程任务后对于编程过程.最终得分的一些感想与经验分享.此外笔者还对于本课程的结对编程部分提出了一些建议. Tips Link 作业要求博客 2 ...
-
sql when null 判断
Sql Server 中使用case when then 判断某字段是否为null,和判断是否为字符或数字时的写法不一样,如果不注意,很容易搞错 错误方法: CASE columnName WHEN ...
-
Alpha冲刺(5/10)——追光的人
1.队友信息 队员学号 队员博客 221600219 小墨 https://www.cnblogs.com/hengyumo/ 221600240 真·大能猫 https://www.cnblogs. ...