题意:给定一些点，求最大三角形面积
View Code
1 /* 2 凸包+最大三角形面积 3 */ 4 #include<stdio.h> 5 #include<string.h> 6 #include<stdlib.h> 7 #include<algorithm> 8 #include<iostream> 9 #include<queue> 10 //#include<map> 11 #include<math.h> 12 using namespace std; 13 typedef long long ll; 14 //typedef __int64 int64; 15 const int maxn = 1000005; 16 const int inf = 0x7fffffff; 17 const double pi=acos(-1.0); 18 struct node{ 19 int x,y; 20 bool operator <( const node & p ) const { 21 return y<p.y||(y==p.y&&x<p.x); 22 } 23 }; 24 node pnt[ maxn ],res[ maxn ]; 25 26 int cross ( node sp,node ep,node op ){ 27 return ( sp.x-op.x )*( ep.y-op.y )-( sp.y-op.y )*( ep.x-op.x ); 28 } 29 30 int dis2( node a,node b ){ 31 return ( a.x-b.x )*( a.x-b.x )+( a.y-b.y )*( a.y-b.y ); 32 } 33 34 int garham( int n ){ 35 int top=1; 36 sort( pnt,pnt+n ); 37 if( n==0 ) return 0; 38 else res[ 0 ]=pnt[ 0 ]; 39 if( n==1 ) return 1; 40 else res[ 1 ]=pnt[ 1 ]; 41 if( n==2 ) return 2; 42 else res[ 2 ]=pnt[ 2 ]; 43 44 for( int i=2;i<n;i++ ){ 45 while( top>0&&cross( res[ top-1 ],pnt[ i ],res[ top ] )>=0 ) 46 top--; 47 res[ ++top ]=pnt[ i ]; 48 } 49 50 int len=top; 51 res[ ++top ]=pnt[ n-2 ]; 52 for( int i=n-3;i>=0;i-- ){ 53 while( top!=len&&cross( res[ top-1 ],pnt[ i ],res[ top ] )>=0 ) 54 top--; 55 res[ ++top ]=pnt[ i ]; 56 } 57 58 return top; 59 } 60 61 int main(){ 62 int n; 63 while( scanf("%d",&n)!=EOF ){ 64 for( int i=0;i<n;i++ ) 65 scanf("%d%d",&pnt[ i ].x,&pnt[ i ].y); 66 int cnt=garham( n ); 67 double ans=0; 68 for( int i=0;i<cnt;i++ ){ 69 for( int j=i+1;j<cnt;j++ ){ 70 for( int k=j+1;k<cnt;k++ ){ 71 ans=max( ans,( 0.5*cross( res[ j ],res[ k ],res[ i ] ) ) ); 72 } 73 } 74 } 75 printf("%.2lf\n",ans); 76 } 77 return 0; 78 }