Grandpa's Estate - POJ 1228(稳定凸包)

时间:2022-09-14 10:49:11

刚开始看这个题目不知道是什么东东,后面看了大神的题解才知道是稳定凸包问题,什么是稳定凸包呢?所谓稳定就是判断能不能在原有凸包上加点,得到一个更大的凸包,并且这个凸包包含原有凸包上的所有点。知道了这个东西就简单了,直接求出来凸包后,然后判断每条边上的点是否超过三点就行了。

代码如下:

============================================================================================================================

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

  1. poj 1228 稳定凸包

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

  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 Grandpa&&num;39&semi;s Estate&lpar;凸包&rpar;

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

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

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

  7. POJ1228 Grandpa&&num;39&semi;s Estate 稳定凸包

    POJ1228 转自http://www.cnblogs.com/xdruid/archive/2012/06/20/2555536.html   这道题算是很好的一道凸包的题吧,做完后会加深对凸包的 ...

  8. ●POJ 1228 Grandpas Estate

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

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

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

随机推荐

  1. C&num;和Javascript的try…catch…finally的一点差别

    C#中规定:如果程序的控制流进入了一个带finally块的try语句,那么finally语句块始终会被执行 例子: class Program { static void Main(string[] ...

  2. LaTex数学符号

    http://web.ift.uib.no/Teori/KURS/WRK/TeX/symALL.html

  3. android 二维码生成

    1,activity public void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); set ...

  4. Winform与WPF对话框&lpar;MessageBox&comma; Dialog&rpar;之比较

    Winform:使用System.Windows.Forms命名空间中相应控件; WPF则调用Microsoft.Win32. MessageBox: // WinForm private void ...

  5. JavaScript总结之单击弹出div

    今天也算用了不少手段来实现他们的要求,大概记录一下,下边的代码示例,我全部修改贴出来,争取全部占到自己的代码里就能用. 1.点击同一个div,打开/关闭另一个div. 1 <script typ ...

  6. pureMVC简单示例及其原理讲解五&lpar;Facade&rpar;

    本节将讲述Facade,Proxy.Mediator.Command的统一管家.自定义Facade必须继承Facade,在本示例中自定义Facade名称为ApplicationFacade,这个名称也 ...

  7. unity加载ab后,场景shader不起效问题&lpar;物件表现黑色&rpar;

    需要把unity自带的shader,加入到默认列表

  8. &lbrack;2019BUAA软件工程&rsqb;结对编程感想

    结对编程感想 写在前面   本博客为笔者在完成软件工程结对编程任务后对于编程过程.最终得分的一些感想与经验分享.此外笔者还对于本课程的结对编程部分提出了一些建议. Tips Link 作业要求博客 2 ...

  9. sql when null 判断

    Sql Server 中使用case when then 判断某字段是否为null,和判断是否为字符或数字时的写法不一样,如果不注意,很容易搞错 错误方法: CASE columnName WHEN ...

  10. Alpha冲刺&lpar;5&sol;10&rpar;——追光的人

    1.队友信息 队员学号 队员博客 221600219 小墨 https://www.cnblogs.com/hengyumo/ 221600240 真·大能猫 https://www.cnblogs. ...