POLYGON

源程序名 POLYGON.??? (PAS,C,CPP)

可執行文件名?? POLYGON.EXE

輸入文件名???? POLYGON.IN

輸出文件名 ????POLYGON.OUT

???

對于一個多邊形來說，在該多邊形內任取兩點，如果這兩點連成的線段落在多邊形內，則稱這樣的多邊形為凸多邊形。

平面上有N個坐標值為自然數的圓點。頂點數最多凸多邊形是指由給定的圓點中的一部分組成的凸多邊形，它包含最大可能的頂點數。原點，即坐標內中心(0，0)必須是頂點數最多凸多邊形的一個頂點。

編寫程序求出這樣的凸多邊形的最大頂點數。注意一個多邊形的連續的邊不能是平行的。

?

輸入

輸入文件的第一行包含一個自然數N，2≤N≤100，表示給定的圓點數。

下面的N行每行包含兩個用空格隔開的自然數X和Y，1≤X≤100，1≤Y≤100，表示一個圓點的坐標值。所有的圓點是不相同的。

?

輸出

輸出文件的第一行也是唯一的一行應該包含頂點數最多凸多邊形的頂點數。注意結果應不小于3。

?

樣例

POLYGON.IN

8

10 8

3 9

2 8

2 3

9 2

9 10

10 3

8 10

?

POLYGON.OUT

8

?

【題解】

有點坑。。第一眼看成求凸包頂點數了結果竟然還有50分= =

然后后面想了半天不會做

然后呢想了半天發現設f[i,j]表示最后兩個點為i和j的情況下凸多邊形最大頂點數

那么枚舉k [1...i-1]即可，f[i,j]即可用f[k,i]更新

更新的情況當且僅當是個凸多邊形（用向量叉積判斷）

1 #include <stdio.h> 2 using namespace std; 3 struct P { 4 int x,y; 5 }p[105]; 6 int n; 7 int f[105][105]; 8 // f i,j 表示凸多邊形的最后兩個頂點為i,j所構成的最多頂點數 9 inline void IO() { 10 freopen("polygon.in","r",stdin); 11 freopen("polygon.out","w",stdout); 12 } 13 inline int max(int a,int b) {return a<b?b:a;} 14 inline void swap(P &a, P &b) { 15 int _tem; 16 _tem=a.x, a.x=b.x, b.x=_tem; 17 _tem=a.y, a.y=b.y, b.y=_tem; 18 } 19 inline int cj(P a, P b) { 20 return a.x*b.y-b.x*a.y; 21 } 22 23 inline void RS() { 24 p[0].x=0, p[0].y=0; 25 scanf("%d",&n); 26 for (int i=1;i<=n;++i) scanf("%d %d",&p[i].x,&p[i].y); 27 //按照斜率排序 28 for (int i=1;i<n;++i) for (int j=i+1;j<=n;++j) 29 if (p[i].x*p[j].y < p[j].x*p[i].y) // y1/x1 > y2/x2 30 swap(p[i],p[j]); 31 for (int i=1;i<=n;++i) f[0][i]=1; 32 for (int i=1;i<=n;++i) 33 for (int j2=i+1;j2<=n+1;++j2) 34 for (int k=0;k<=i-1;++k) { 35 int j; 36 P _x, _y; int _tem; 37 if (j2==n+1) j=0; 38 else j=j2; 39 _x.x=p[i].x-p[k].x, _x.y=p[i].y-p[k].y; 40 _y.x=p[j].x-p[i].x, _y.y=p[j].y-p[i].y; 41 int c = cj(_y,_x); 42 if (c<0) f[i][j]=max(f[i][j],f[k][i]+1); 43 } 44 int ans=0; 45 for (int i=0;i<=n;++i) 46 for (int j2=i+1;j2<=n+1;++j2) { 47 int j; 48 if (j2==n+1) j=0; else j=j2; 49 ans = max(ans,f[i][j]); 50 } 51 printf("%d\n",ans); 52 } 53 int main() { 54 IO(), 55 RS(); 56 return 0; 57 } View Code

?

轉載于:https://www.cnblogs.com/TonyNeal/p/noip_polygon.html

總結

以上是生活随笔為你收集整理的[Noip模拟赛] Polygon的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。