首页 > 代码库 > poj2079Triangle(N点中三点组成三角形面积最大)

poj2079Triangle(N点中三点组成三角形面积最大)

链接

根据旋转卡壳的思想,找到当前边的最远点。

确定i,j找到最远的k使 cross(i,j,k)最大,那么i,j+1时只需从k+1开始找即可 。

  1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 50010 12 #define LL long long 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 struct point 18 { 19     int x,y; 20     point(int x=0,int y=0):x(x),y(y) {} 21 } p[N],ch[N]; 22 typedef point pointt; 23 pointt operator - (point a,point b) 24 { 25     return point(a.x-b.x,a.y-b.y); 26 } 27 int dcmp(double x) 28 { 29     if(fabs(x)<eps) return 0; 30     return x<0?-1:1; 31 } 32 double cross(point a,point b) 33 { 34     return 1.0*a.x*b.y-1.0*a.y*b.x; 35 } 36 double getarea(point a,point b,point c) 37 { 38     return fabs(cross(b-a,c-a))/2; 39 } 40 double mul(point p0,point p1,point p2) 41 { 42     return cross(p1-p0,p2-p0); 43 } 44 double dis(point a) 45 { 46     return sqrt(1.0*a.x*a.x+a.y*a.y); 47 } 48 bool cmp(point a,point b) 49 { 50     if(dcmp(mul(p[0],a,b))==0) return dis(a-p[0])<dis(b-p[0]); 51     return dcmp(mul(p[0],a,b))>0; 52 } 53 int graham(int n) 54 { 55     int i,k=0,top; 56     point tmp; 57     for(i = 0;  i< n; i++) 58     { 59         if(p[i].y<p[k].y||(p[i].y==p[k].y&&p[i].x<p[k].x)) 60             k = i; 61     } 62     if(k!=0) 63         swap(p[0],p[k]); 64     sort(p+1,p+n,cmp); 65     ch[0] = p[0]; 66     ch[1] = p[1]; 67     top = 1; 68     for(i = 2; i < n; i++) 69     { 70         while(top>0&&dcmp(mul(ch[top-1],ch[top],p[i]))<=0) 71             top--; 72         ch[++top] = p[i]; 73     } 74     return top; 75 } 76 int main() 77 { 78     int n,i,j,k,kk; 79     while(scanf("%d",&n)!=EOF) 80     { 81         if(n==-1) break; 82         for(i = 0; i < n; i++) 83             scanf("%d%d",&p[i].x,&p[i].y); 84         int top = graham(n); 85         double maxz=0,area; 86     ++top; 87     ch[top] = ch[0]; 88     for(i=0; i<top; ++i) 89     { 90         j=(i+1)%top; 91         k=(j+1)%top; 92         while(k!=i && getarea(ch[i],ch[j],ch[k])<getarea(ch[i],ch[j],ch[k+1])) 93             k=(k+1)%top; 94         maxz = max(maxz,getarea(ch[i],ch[j],ch[k])); 95         if(k == i) 96             continue; 97         kk=(k+1)%top; 98         while(j!=kk && k!=i) 99         {100             area=getarea(ch[i],ch[j],ch[k]);101             if(area>maxz)102                 area=maxz;103             while(k!=i && getarea(ch[i],ch[j],ch[k])<getarea(ch[i],ch[j],ch[k+1]))104                 k=(k+1)%top;105             maxz = max(maxz,getarea(ch[i],ch[j],ch[k]));106             j=(j+1)%top;107         }108     }109     printf("%.2f\n",maxz);110 111     }return 0;112 }
View Code