[计算几何]Grandpa's Estate[POJ1228]

欢迎大家访问我的老师的OJ———caioj.cn

题目描述

网上代码大部分都过不了这个数据

4
6
1 1 2 2 3 3 4 4 5 5 6 6
1
1 1
8
0 0 0 1 0 2 0 3 1 1 2 2 3 3 2 3
8
0 0 0 2 1 0 1 2 2 2 3 0 3 1 3 2

好题

可惜数据太水了

题解明天再写。

主要思路就是:

（1）此题需要判断“凸包上每条边至少包含原多边形三个点”。成立就是“YES”。
（2）注意：所有点共线时，结果为“NO”。
（3）另外由上面（1）判断可的，n<=5时，结果为"NO"。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define eps 1e-8
using namespace std;
const int N=1010;
struct node{double x,y;}p[N],h[N];
bool cmp(node a,node b){return a.x==b.x?a.y<b.y:a.x<b.x;}
int tp,n,sta[N];bool v[N];
double mul(node p1,node p2,node p0)
{
	double x1=p1.x-p0.x,y1=p1.y-p0.y;
	double x2=p2.x-p0.x,y2=p2.y-p0.y;
	return x1*y2-x2*y1;
}
void tb()
{
	tp=0;sort(p+1,p+n+1,cmp);
	sta[++tp]=1;
	for(int i=2;i<=n;i++)
	{
		while(tp>1&&mul(p[sta[tp]],p[i],p[sta[tp-1]])<0)v[sta[tp--]]=0;
		v[i]=1;sta[++tp]=i;
	}
	int top=tp;
	for(int i=n-1;i;i--)
		if(!v[i])
		{
			while(tp>top&&mul(p[sta[tp]],p[i],p[sta[tp-1]])<0)v[sta[tp--]]=0;
			sta[++tp]=i;
		}
	for(int i=1;i<=tp;i++)h[i]=p[sta[i]];
}
bool is_line()
{
	bool bk=true;
	for(int i=1;i<tp-1;i++)
		if(fabs(mul(h[i+2],h[i+1],h[i-1]))>eps)bk=false;
	return bk;
}
bool pd()
{
	if(fabs(mul(h[tp-1],h[tp],h[tp-2]))>eps&&fabs(mul(h[tp],h[1],h[tp-1]))>eps)return false;
	if(fabs(mul(h[tp],h[1],h[tp-1]))>eps&&fabs(mul(h[1],h[2],h[tp]))>eps)return false;
	if(fabs(mul(h[1],h[2],h[tp]))>eps&&fabs(mul(h[2],h[3],h[1]))>eps)return false;
	for(int i=2;i<tp-1;i++)
		if(fabs(mul(h[i],h[i+1],h[i-1]))>eps&&fabs(mul(h[i+1],h[i+2],h[i]))>eps)
			return false;
	return true;
}
int main()
{
	int t;scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
		tb();tp--;
		if(!pd()||n<=5||is_line())puts("NO");
		else puts("YES");
	}
	return 0;
}