天河营销型网站建设,如何购买云服务器,建行国际互联网网站,中信建设有限责任公司招聘POJ 1228 Grandpas Estate 这是个好题目#xff0c;同时也是个不和谐的题目#xff08;不和谐原因是题目出的存在漏洞#xff0c;数据弱#xff0c;而且有些条件没给清楚#xff0c;为了一个SB错误无限WA之后#xff0c;终于AC#xff09; 题意就废了我好长时间#xf…POJ 1228 Grandpas Estate 这是个好题目同时也是个不和谐的题目不和谐原因是题目出的存在漏洞数据弱而且有些条件没给清楚为了一个SB错误无限WA之后终于AC 题意就废了我好长时间唉……英语不好的鸭梨大…… 大意就是爷爷留了块土地给我然而这块土地是以一些钉子来界定的题目要做的就是给你一堆钉子的坐标也就是凸包上部分的点然后问你能不能唯一确定这块土地。 问了下度娘这个问题叫做“稳定”凸包问题那么首先就要了解下“稳定”凸包的性质在此感谢XDruid博主 比方说有4个点 这4个点可以围成一个凸包但是原始的凸包可能并不是这个样子的 例如可能是这个样子 这样我们则称这4个点确定的凸包是”不稳定“的 那么怎么样才叫稳定呢 是这个样子想一想若像刚才一样在直线外面加一个点那么线上的点必定不会属于凸包要删掉是吧 如此以来问题就很明确了算法也随之而来了 我们已经知道了怎么求凸包了前提这样一来只要判断是否有3点或N3点共线就可以了~~ 表示用的是Graham的变种Andrew……感觉真的很好用 下面贴代码 View Code #include cstdio
#include algorithm
#include cmath
using namespace std;const double EPS 1e-6;struct point{double x , y;
} p[1010] , chn[1010];bool cmp (point a , point b)
{return (a.y b.y || (a.y b.y a.x b.x));
}double xmult(point p1 , point p2 , point p3)
{return ((p1.x - p3.x) * (p2.y - p3.y) - (p1.y - p3.y) * (p2.x - p3.x));
}int andrew(int n)
{int len , top 1;chn[0] p[0];chn[1] p[1];for (int i 2 ; i n ; i ){while (top xmult(p[i] , chn[top] , chn[top - 1]) EPS) top --;chn[ top] p[i];}len top;chn[ top] p[n - 2];for (int i n - 3 ; i 0 ; i --){while (top ! len xmult(p[i] , chn[top] , chn[top - 1]) EPS) top --;chn[ top] p[i];}return top;
}bool judge(int n) //解释请看下面
{for (int i 1 ; i n ; i ){if ((xmult(chn[i - 1] , chn[i] , chn[i 1]) ! 0) (xmult(chn[i] , chn[i 1] , chn[i 2]) ! 0))return false;}return true;
}int main()
{int T , n;scanf(%d , T);while (T --){scanf(%d , n);for (int i 0 ; i n ; i ) scanf(%lf%lf , p[i].x , p[i].y);if (n 6) printf(NO\n);else{sort(p , p n , cmp);int top andrew(n);if (judge(top)) printf(YES\n);else printf(NO\n);}}return 0;
} 写了这个题后对凸包的理解真是加深了。 同时在被WA了N此后主要是因为读入数据要用double。但是题目上说是整点啊不明白如果没看到别人的解题报告估计要一直WA下去 昨晚在无限WA后找了XxX师兄开始以为思路错了经过他的问答对这个题目的理解更是加深了 下面说下代码中【judge】函数的判断原因 理论支持叉积 0 说明共线 我们用Andrew算法求出凸包后栈内不删去共线的点这些点已经是按一定顺序排好了的~ 然后之需要对栈内的点进行叉积判断就可以了~~ 只有当向左与向中间扩展都不满足是才说明当前点不满足 所以只要有一个不满足则说明全部不满足了。 做了这个题目我对之前提出的疑问有了答案。哈哈~~转载于:https://www.cnblogs.com/hmhard/archive/2013/02/07/2908860.html
