首页 > 代码库 > 凸多边形的最大顶点数
凸多边形的最大顶点数
对于一个多边形来说，在该多边形内任取两点，如果这两点连成的线段落在多边形内，则称这样的多边形为凸多边形。
平面上有N个坐标值为自然数的圆点。顶点数最多凸多边形是指由给定的圆点中的一部分组成的凸多边形，它包含最大可能的顶点数。原点，即坐标内中心(0，0)必须是顶点数最多凸多边形的一个顶点。
编写程序求出这样的凸多边形的最大顶点数。注意一个多边形的连续的边不能是平行的。
输入
输入文件的第一行包含一个自然数N，2≤N≤100，表示给定的圆点数。
下面的N行每行包含两个用空格隔开的自然数X和Y，1≤X≤100，1≤Y≤100，表示一个圆点的坐标值。所有的圆点是不相同的。
输出
输出文件的第一行也是唯一的一行应该包含顶点数最多凸多边形的顶点数。注意结果应不小于3。
样例
输入：
8
10 8
3 9
2 8
2 3
9 2
9 10
10 3
8 10
输出：
8
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstdio> 5 using namespace std ; 6 int n ; 7 struct id{ 8 int x , y ; 9 } pin[105] ;10 int f[105][105] ;11 12 bool cmp( id a , id b ) {13 if( a.x * b.y < a.y * b.x ) return 1 ;14 return 0 ;15 }16 17 int main ( ) {18 // freopen( "10039.in" , "r" , stdin ) ;19 // freopen( "10039.out" , "w" ,stdout ) ;20 scanf( "%d" , &n ) ;21 for( int x = 1 ; x <= n ; x++ ) scanf( "%d%d" , &pin[x].x , &pin[x].y ) ;22 sort( pin + 1 , pin + 1 + n , cmp ) ;23 for( int x = 1 ; x <= n ; x++ ) f[0][x] = 1 ;24 for( int i = 1 ; i <= n ; i++ ) 25 for( int j = i+1 ; j <= n+1 ; j++ ) 26 for( int k = 0 ; k <= i-1 ; k++ ) {27 int x ;28 id a , b ; int tem ;29 if( j == n+1 ) x = 0 ;30 else x = j;31 a.x = pin[i].x - pin[k].x, a.y = pin[i].y - pin[k].y;32 b.x = pin[x].x-pin[i].x, b.y = pin[x].y - pin[i].y;33 int c = a.x * b.y - b.x*a.y ;34 if (c<0) f[i][x] = max( f[i][x], f[k][i]+1 ); 35 }36 37 38 int ans = 0;39 for ( int i = 0; i <= n; ++i )40 for ( int j2 = i+1; j2 <= n+1; ++j2 ) {41 int j ;42 if ( j2 == n+1 ) j = 0 ; else j = j2 ;43 ans = max( ans, f[i][j] ) ; 44 }45 printf("%d\n",ans); 46 return 0 ;47 }
凸多边形的最大顶点数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。