就是给你一堆点,看这些点能否构成一个 稳定的凸包。
凸包每条边上有3个及以上的点就可以了。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 typedef double db; 9 const db eps = 1e-6;10 const db pi = acos(-1);11 using namespace std;12 int sign(db k){13 if (k>eps) return 1; else if (k<-eps) return -1; return 0;14 }15 int cmp(db k1,db k2){ return sign(k1-k2);}16 int inmid(db k1,db k2,db k3){ return sign(k1-k3)*sign(k2-k3)<=0;}// k3 在 [k1,k2] 内17 struct point{18 db x,y;19 point operator + (const point &k1) const{ return (point){k1.x+x,k1.y+y};}20 point operator - (const point &k1) const{ return (point){x-k1.x,y-k1.y};}21 point operator * (db k1) const{ return (point){x*k1,y*k1};}22 point operator / (db k1) const{ return (point){x/k1,y/k1};}23 bool operator <(const point &k1)const {24 int c=cmp(x,k1.x);25 if(c)return c==-1;26 return cmp(y,k1.y)==-1;27 }28 };29 int inmid(point k1,point k2,point k3){ return inmid(k1.x,k2.x,k3.x)&&inmid(k1.y,k2.y,k3.y);}30 db cross(point k1,point k2){ return k1.x*k2.y-k1.y*k2.x;}31 db dot(point k1,point k2){ return k1.x*k2.x+k1.y*k2.y;}32 vector convexHull(vector ps){33 int n = ps.size();if(n<=1)return ps;34 sort(ps.begin(),ps.end());35 vector qs(n*2);int k=0;36 for(int i=0;i 1&&cross(qs[k-1]-qs[k-2],ps[i]-qs[k-2])<=0)--k;38 for(int i=n-2,t=k;i>=0;qs[k++]=ps[i--])39 while (k>t&&cross(qs[k-1]-qs[k-2],ps[i]-qs[k-2])<=0)--k;40 qs.resize(k-1);41 return qs;42 }43 vector v;44 int t,n;45 point p[1005];46 point tmp;47 int main(){48 scanf("%d",&t);49 while (t--){50 scanf("%d",&n);51 for(int i=1;i<=n;i++){52 scanf("%lf%lf",&tmp.x,&tmp.y);53 v.push_back(tmp);54 p[i]=tmp;55 }56 v=convexHull(v);57 int m = v.size();58 bool f=1;59 for(int i=0;i