首页 > 代码库 > poj1228稳定凸包
poj1228稳定凸包
就是给一系列点,看这是不是一个稳定凸包
稳定凸包是指一个凸包不能通过加点来使它扩大面积,也就是说每条边最少有三个点
判断的地方写错了,写了两边循环,其实数组s已经排好了序,直接每三个判断就好了
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cassert> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-7; const int N=1000+10,maxn=500+100,inf=0x3f3f3f; struct point{ double x,y; }; point p[N],s[N]; int n; double dir(point p1,point p2,point p3) { return (p3.x-p1.x)*(p2.y-p1.y)-(p3.y-p1.y)*(p2.x-p1.x); } double dis(point p1,point p2) { return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); } bool comp(point p1,point p2) { double te=dir(p[0],p1,p2); if(te<0)return 1; if(te==0&&dis(p[0],p1)<dis(p[0],p2))return 1; return 0; } bool graham() { int pos; double minx,miny; minx=miny=inf; for(int i=0;i<n;i++) { if(p[i].y<miny||(p[i].y==miny&&p[i].x<minx)) { minx=p[i].x; miny=p[i].y; pos=i; } } swap(p[0],p[pos]); sort(p+1,p+n,comp); int top=2; p[n]=p[0]; s[0]=p[0],s[1]=p[1],s[2]=p[2]; for(int i=3;i<=n;i++) { while(top>=2&&dir(s[top-1],s[top],p[i])>0)top--; s[++top]=p[i]; } /* cout<<endl; for(int i=0;i<n;i++) cout<<p[i].x<<" "<<p[i].y<<endl; cout<<endl; for(int i=0;i<top;i++) cout<<s[i].x<<" "<<s[i].y<<endl;*/ for(int i=1;i<top-1;i++) { if(dir(s[i-1],s[i],s[i+1])!=0&&dir(s[i],s[i+1],s[i+2])!=0) return 0; } return 1; } int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin>>t; while(t--){ cin>>n; for(int i=0;i<n;i++) cin>>p[i].x>>p[i].y; if(n<6) { cout<<"NO"<<endl; continue; } if(graham())cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; } /* 1 4 0 1 0 2 0 3 0 4 */
poj1228稳定凸包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。