543
技術社區[雲棲]
POJ 1228 凸包
這題考察凸包的理解，題意讓求一個凸包上每條邊都有三個點，如果少於三個點那麼凸包就不確定了，三點以上如果再加一個點就形成不了凸包了。通過極角排序完然後求跟凸包的相鄰兩點共線的點有沒有就可以了，寫得比較挫。。。
（1）此題需要判斷“凸包上每條邊至少包含原多邊形三個點”。成立就是“YES”。
我試的判斷“多邊形上 所有點 在凸包上”，WA！！
（2）注意：所有點共線時，結果為“NO”。
（3）另外由上麵（1）判斷可的，n<=5時，結果為"NO"。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double PointType;
struct point
{
PointType x,y;
int num;
};
point data[1005],stack[1005],MinA;
int top;
PointType Direction(point pi,point pj,point pk) //判斷向量PiPj在向量PiPk的順逆時針方向 +順-逆0共線
{
return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
PointType Dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(point a,point b)
{
PointType k=Direction(MinA,a,b);
if(k>0) return 1;
if(k<0) return 0;
return Dis(MinA,a)>Dis(MinA,b);
}
void Graham_Scan(point *a,int numa)
{
for(int i=0; i<numa; i++)
if(a[i].y<a[0].y||(a[i].y==a[0].y&&a[i].x<a[0].x))
swap(a[i],a[0]);
MinA=a[0],top=0;
sort(a+1,a+numa,cmp);
stack[top++]=a[0],stack[top++]=a[1],stack[top++]=a[2];
for(int i=3; i<numa; i++)
{
while(Direction(stack[top-2],stack[top-1],a[i])<0)
top--;
stack[top++]=a[i];
}
}
bool judgeline(int n)
{
for(int i=2; i<n; i++)
if(Direction(data[i-2],data[i-1],data[i]))
return 0;
return 1;
}
int main()
{
int n,t,m;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0; i<n; i++)
scanf("%lf%lf",&data[i].x,&data[i].y);
if(n<6||judgeline(n))
{
puts("NO");
continue;
}
Graham_Scan(data,n);
int f=1;
for(int i=0,j=0; i<top; i++)
{
int num=0;
if(i<top-1)
{
for(int j=0; j<n; j++)
if(!Direction(stack[i],stack[i+1],data[j]))
num++;
}
else
for(int j=0; j<n; j++)
if(!Direction(stack[i],stack[0],data[j]))
num++;
if(num<3)
{
f=0;
break;
}
}
puts(f?"YES":"NO");
}
return 0;
}
最後更新：2017-04-03 22:15:29