首页 > 代码库 > 【POJ】1228 Grandpa's Estate（凸包）
【POJ】1228 Grandpa's Estate（凸包）
http://poj.org/problem?id=1228
随便看看就能发现，凸包上的每条边必须满足，有相邻的边和它斜率相同（即共线或凸包上每个点必须一定在三点共线上）
然后愉快敲完凸包+斜率判定，交上去wa了QAQ。原因是忘记特判一个地方....因为我们求的凸包是三点共线的凸包，在凸包算法中我们叉积判断只是>0而不是>=0，那么会有一种数据为所有点共线的情况，此时求出来的凸包上的点是>原来的点的（此时恰好符合答案NO，因为可以在这条线外随便点一个点就是一个凸包了...）然后特判一下..
就过了..
证明很简单：如果这条边没有3个点及以上，那么必然可以在边外点一个点成为新的凸包。
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }struct ipt { int x, y; };int icross(ipt &a, ipt &b, ipt &c) { static int x1, x2, y1, y2; x1=a.x-c.x; y1=a.y-c.y; x2=b.x-c.x; y2=b.y-c.y; return x1*y2-x2*y1;}bool cmp(const ipt &a, const ipt &b) { return a.x==b.x?a.y<b.y:a.x<b.x; }void tu(ipt *p, ipt *s, int n, int &top) { sort(p, p+n, cmp); top=-1; rep(i, n) { while(top>0 && icross(p[i], s[top], s[top-1])>0) --top; s[++top]=p[i]; } static int k; k=top; for3(i, n-2, 0) { while(top>k && icross(p[i], s[top], s[top-1])>0) --top; s[++top]=p[i]; } if(n>1) --top; ++top;}const int N=1005;ipt a[N], b[N];int n;int main() { int ca=getint(); while(ca--) { read(n); int ttt=n; rep(i, n) read(a[i].x), read(a[i].y); //dbg(n); if(n<=2) { puts("NO"); continue; } tu(a, b, n, n); if(n>ttt) { puts("NO"); continue; } //dbg(n); b[n]=b[0]; int up=b[1].x-b[0].x, down=b[1].y-b[0].y, cnt=1, flag=1; for1(i, 1, n-1) { int uup=b[i+1].x-b[i].x, ddown=b[i+1].y-b[i].y; // printf("%d:(%d,%d)\n", i, b[i].x, b[i].y); if(up*ddown!=uup*down) { if(cnt<2) { flag=0; break; } up=uup; down=ddown; cnt=1; } else ++cnt; } if(cnt<2) flag=0; flag?puts("YES"):puts("NO"); } return 0;}
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 16 0 01 23 42 02 4 5 0 Sample Output NO Source Tehran 2002 Preliminary |
【POJ】1228 Grandpa's Estate（凸包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。