首页 > 代码库 > POJ 1228

POJ 1228

2024-07-15 04:06:07   219人阅读

给题意跪了。。。

题目输入一个凸包上的点（没有凸包内部的点，要么是凸包顶点，要么是凸包边上的点），判断这个凸包是否稳定。所谓稳定就是判断能不能在原有凸包上加点，

得到一个更大的凸包，并且这个凸包包含原有凸包上的所有点。

 

这样，只需判断每条边是否有大于等于三点即可。注意，一条直线的凸包是NO

#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;struct point {	int x,y;}p[1050];int n;int stop,cnt;int ans[1050],st[1050];bool cmp(point A,point B){	if(A.y<B.y) return true;	else if(A.y==B.y){		if(A.x<B.x) return true;	}	return false;}bool multi(point a,point b,point c){	return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x)>0;}void slove(){	stop=cnt=0;	st[stop++]=0; st[stop++]=1;	for(int i=2;i<n;i++){		while(stop>1&&multi(p[i],p[st[stop-1]],p[st[stop-2]])) stop--;		st[stop++]=i;	}	for(int i=0;i<stop;i++)	ans[cnt++]=st[i];	stop=0;	st[stop++]=n-1; st[stop++]=n-2;	for(int i=n-3;i>=0;i--){		while(stop>1&&multi(p[i],p[st[stop-1]],p[st[stop-2]])) stop--;		st[stop++]=i;	}	for(int i=1;i<stop;i++)	ans[cnt++]=st[i];}int main(){	int t;	scanf("%d",&t);	while(t--){		scanf("%d",&n);		for(int i=0;i<n;i++){			scanf("%d%d",&p[i].x,&p[i].y);		}		sort(p,p+n,cmp);		slove();/*		for(int i=0;i<cnt;i++){			cout<<p[ans[i]].x<<‘ ‘<<p[ans[i]].y<<endl;		}*/		if(n==1||n==2) { printf("NO\n"); continue; }		bool flag=true; point s,t,e; int k;		s=p[ans[0]]; t=p[ans[1]];		int j;		for(j=2;j<cnt;j++){			e=p[ans[j]];			if((e.x-s.x)*(t.y-s.y)-(e.y-s.y)*(t.x-s.x)!=0){				break;			}		}		if(j>=cnt) { printf("NO\n"); continue; }		for(int i=0;;i=k-1){			s=p[ans[i]];t=p[ans[++i]];			if(i+1>=cnt){ flag=false; break; }		 	e=p[ans[i+1]];			if((e.x-s.x)*(t.y-s.y)-(e.y-s.y)*(t.x-s.x)!=0){				flag=false;				break;			}			k=i+1;			while(true){				e=p[ans[k]];				if((e.x-s.x)*(t.y-s.y)-(e.y-s.y)*(t.x-s.x)!=0){					break;				}				k++;				if(k>=cnt) break;			}			if(k>=cnt) break;		}		if(flag) printf("YES\n");		else printf("NO\n");	}	return 0;}

　　


联系
我们