题目链接poj.org/problem?id=1228
作为祖父唯一活着的后代,信徒卡姆兰继承了祖父的所有财产。最有价值的是爷爷出生村的一块凸面形农场。农场最初被一根厚厚的绳子与邻近的农场隔开,绳子钩在多边形边界上的一些尖刺(大钉子)。但是,当卡姆兰去参观他的农场时,他注意到绳子和一些尖峰不见了。你的任务是编写一个程序来帮助Kamran决定他的农场的边界是否只能由剩余的峰值决定。
输入
输入文件的第一行包含单个整数 t (1 <= t <= 10),测试用例数,后跟每个测试用例的输入数据。每个测试用例的第一行包含一个整数 n (1 <= n <= 1000),这是剩余峰值的数量。接下来,有 n 条线,每个尖峰一条线,每条线包含一对整数,这些整数是尖峰的 x 和 y 坐标。
输出
每个测试用例应该有一个输出行,其中包含 YES 或 NO,具体取决于服务器场的边界是否可以从输入中唯一确定。
Sample Input
1
6
0 0
1 2
3 4
2 0
2 4
5 0
Sample Output
NO
题意理解
给你一堆点,这堆点本来就是某个凸包上的部分点,问你这堆点是否能确定唯一的凸包 。
这个题涉及到一些关于稳定凸包的概念(可以百度一下)。
下面引用大佬博客关于稳定凸包的讲解
首先来了解什么是稳定的凸包。比如有4个点:
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIn5GcsQXYtJ3bm9CXldWYtlWPzNXZj9mcw1ycz9WL49jb1c0Y1VEVOlXRE1UeBRUT3lkaOdXSU10dJpHTzkleORTQE5kdJRVT3lkeMpnVyoFaxcVY2BjMipWN5Nmb5ckYpVjMZVXSE10dNdVY3lTeMZTTINGMShUYvwlbj5yZtlmbkN3YuQnclZnbvN2Ztl2Lc9CX6MHc0RHaiojIsJye.jpg)
这四个点是某个凸包上的部分点,他们连起来后确实还是一个凸包。但是原始的凸包可能不是这样。比如:
即这四个点构成的凸包不算做“稳定”的。我们发现,当凸包上存在一条边上的点只有端点两个点的时候,这个凸包不是稳定的,因为它可以在这条边外再引入一个点,构成一个新的凸包。但一旦一条边上存在三个点,那么不可能再找到一个点使它扩展成一个新的凸包,否则构成的新多边形将是凹的。
下面是一个典型的稳定凸包:
之后这个题就很好做了,求出凸包后,对每一条边判断边上是否有至少3个点,注意考虑大多数模版都不包含共线的情况,要修改一下,其实就是把判断去点里面叉乘等于0的情况加上了。
抛代码(末尾有样例)
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=1000;
struct point
{
int x,y;
};
point list[MAXN];
int stack[MAXN],top;
int cross(point p0,point p1,point p2) //计算叉积 p0p1 X p0p2
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
double dis(point p1,point p2) //计算 p1p2的 距离
{
return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
bool cmp(point p1,point p2) //极角排序函数 , 角度相同则距离小的在前面
{
int tmp=cross(list[0],p1,p2);
if(tmp>0) return true;
else if(tmp==0&&dis(list[0],p1)<dis(list[0],p2)) return true;
else return false;
}
void init(int n) //输入,并把 最左下方的点放在 list[0] 。并且进行极角排序
{
int i,k;
point p0;
scanf("%d%d",&list[0].x,&list[0].y);
p0.x=list[0].x;
p0.y=list[0].y;
k=0;
for(i=1;i<n;i++)
{
scanf("%d%d",&list[i].x,&list[i].y);
if( (p0.y>list[i].y) || ((p0.y==list[i].y)&&(p0.x>list[i].x)) )
{
p0.x=list[i].x;
p0.y=list[i].y;
k=i;
}
}
list[k]=list[0];
list[0]=p0;
sort(list+1,list+n,cmp);
}
void graham(int n)
{
int i;
if(n==1) {top=0;stack[0]=0;}
if(n==2)
{
top=1;
stack[0]=0;
stack[1]=1;
}
if(n>2)
{
for(i=0;i<=1;i++) stack[i]=i;
top=1;
for(i=2;i<n;i++)
{
while(top>0&&cross(list[stack[top-1]],list[stack[top]],list[i])<0) top--;
top++;
stack[top]=i;
}
}
}
int main()
{
int T,N;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
init(N);
graham(N);
if(N<6){
printf("NO\n");
continue;
}
int flag=1;
for(int i=1;i<top;i++){
if(cross(list[stack[i-1]],list[stack[i+1]],list[stack[i]])!=0
&&cross(list[stack[i]],list[stack[i+2]],list[stack[i+1]])!=0){
flag=0;
break;
}
}
if(flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
/*
Input:
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
Output:
YES
NO
YES
YES
*/