正文
Grandpa's Estate---POJ1228(凸包)
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
http://poj.org/problem?id=1228
学长说这是稳定凸包，我感觉就是凸包嘛。
所谓稳定就是判断能不能在原有凸包上加点，得到一个更大的凸包，并且这个凸包包含原有凸包上的所有点。知道了这个东西就简单了，直接求出来凸包后，然后判断每条边上的点是否超过三点就行了。------无忧望月。
这道题的题也是看都看不懂，反正就是求凸包的每个边至少有三个点
还有如果是只有一条线的话输出NO
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue> using namespace std;
#define N 1005
#define pi acos(-1.0)
#define ESP 1e-8 int s[N]; struct Point
{
double x,y;
Point(double x=,double y=):x(x),y(y){}
Point operator - (const Point &temp)const
{
return Point(x-temp.x,y-temp.y);
}
Point operator + (const Point &temp)const
{
return Point(x+temp.x,y+temp.y);
}
bool operator == (const Point &temp)const
{
return (x==temp.x && y==temp.y);
}
double operator * (const Point &temp)const
{
return (x*temp.x+y*temp.y);
}
int operator ^ (const Point &temp)const{
double t=x*temp.y-y*temp.x;
if(t>ESP)
return ;
if(fabs(t)<ESP)
return ;
return -;
}
}p[N]; double dist(Point a,Point b)
{
return sqrt((a-b)*(a-b));
} int cmp(Point a1,Point a2)
{
int t=((a1-p[])^(a2-p[]));
if(t==)
return dist(a1,p[])<dist(a2,p[]);
else
return t>;
}
int top;
void Graham(int n)///求凸包
{
s[]=;
s[]=;
top=;
for(int i=;i<n;i++)
{
while(top> && ((p[i]-p[s[top]])^(p[s[top-]]-p[s[top]]))<=)
top--;
s[++top]=i;
}
} int main()
{ int T,n;
scanf("%d",&T);
while(T--)
{
int k=;
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%lf %lf",&p[i].x,&p[i].y);
if(p[i].y<p[k].y || (p[i].y==p[k].y && p[i].x<p[k].x))
k=i;
}
swap(p[],p[k]);
sort(p+,p+n,cmp);
Graham(n);
s[++top]=s[];
int flag=;
for(int i=;i<=top;i++)
{
int ans=;
for(int j=;j<n;j++)
{
if(((p[j]-p[s[i]]) ^ (p[s[i-]]-p[s[i]]))==)
ans++;
}
if(ans<)
{
flag=;
break;
}
}
if(flag== && top>=)
printf("YES\n");
else
printf("NO\n");
}
return ;
}
