題目：Grandpa's Estate

?

題意：輸入一個凸包上的點（沒有凸包內(nèi)部的點，要么是凸包頂點，要么是凸包邊上的點），判斷這個凸包是否穩(wěn)定。所謂穩(wěn)

定就是判斷能不能在原有凸包上加點，得到一個更大的凸包，并且這個凸包包含原有凸包上的所有點。

?

分析：容易知道，當(dāng)一個凸包穩(wěn)定時，凸包的每條邊上都要有至少三個點，若只有兩個點，則可以增加一個點，得到更大的凸

包。這樣我們可以求出凸包，在求凸包時把共線的點也加進來，這樣我們就判斷是否有連續(xù)的三點共線即可，具體參見代碼。

#include <iostream> #include <algorithm> #include <stdio.h> #include <math.h>using namespace std;const int N = 40005;typedef double DIY;struct Point {DIY x,y; };Point p[N]; Point stack[N]; Point MinA;int top;DIY dist(Point A,Point B) {return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)); }DIY cross(Point A,Point B,Point C) {return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x); }bool cmp(Point a,Point b) {DIY k=cross(MinA,a,b);if(k>0) return 1;if(k<0) return 0;return dist(MinA,a)<dist(MinA,b); //這里共線的點按距離從小到大排序 }void Graham(int n) {int i;for(i=1; i<n; i++)if(p[i].y<p[0].y||(p[i].y==p[0].y&&p[i].x<p[0].x))swap(p[i],p[0]);MinA=p[0];sort(p+1,p+n,cmp);stack[0]=p[0];stack[1]=p[1];top=1;for(i=2; i<n; i++){//注意這里我們把共線的點也壓入凸包里while(cross(stack[top-1],stack[top],p[i])<0&&top>=1) --top;stack[++top]=p[i];} }bool Judge() {for(int i=1;i<top;i++){//判斷凸包的一條邊上是否至少有3點if((cross(stack[i-1],stack[i+1],stack[i]))!=0&&(cross(stack[i],stack[i+2],stack[i+1]))!=0)return false;}return true; }int main() {int t,n,i;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);if(n<6){puts("NO");continue;}Graham(n);cout<<endl;for(i=0;i<n;i++)cout<<p[i].x<<" "<<p[i].y<<endl;cout<<endl;for(i=0;i<=top;i++)cout<<stack[i].x<<" "<<stack[i].y<<endl;if(Judge()) puts("YES");else puts("NO");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ1228(稳定凸包问题)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。