coreBugZJ

此 blog 已弃。

Summer holiday, 1005, 2011 Multi-University Training Contest 10

Summer holiday

TimeLimit: 1 Second   MemoryLimit: 32 Megabyte

Totalsubmit: 434   Accepted: 108  

Description

Summer holiday was coming! Xiaomao went back to his hometown where he yearn day and night, his hometown has picturesque scenery. There is a big forest beside his village. There are n trees in the forest.
Now they want to across the forest with a rope (the rope won't cross). Try to find 3 trees in this tree on the rope which can make the area of the surrounded largest. Work out the area of it.


Input

The input will consist of several test cases. The first line contains a positive integer N(3<=N<=10^6), the number of trees, followed N lines, each gives the (xi, yi ) coordinates.


Output

Print the largest area, one number a line with two decimal places.


Sample Input

4
0 0
1 1
0 1
1 0


Sample Output

0.50


Source

[p][/p]




二维凸包


不做 ACM 三个月了,心血来潮参加了练习赛,悲剧的没有准备模板,这个模板是临时从网上搜来的,非原创。


  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstdlib>
  5 #include<algorithm>
  6 
  7 using namespace std;
  8 
  9 struct P{
 10         double x,y;
 11 };
 12 
 13 #define  EPS  0.00001
 14 #define  ZERO(x)   ( (x<EPS) && ((-(x))<EPS) )
 15 
 16 const int L = 2000009;
 17 P p[ L ], stack[ L ];
 18 int n, top;
 19 
 20 inline double Mul(P p1,P p2,P p3) 
 21 {    
 22         return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x); 
 23 }
 24 
 25 inline double dis(P a,P b)
 26 {
 27         return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
 28 }
 29 
 30 int cmp(const void *a,const void *b)
 31 {
 32         P * c = (P *)a;
 33         P * d = (P *)b;
 34         double k = Mul(p[0],*c,*d);
 35         if(k<0 || (!&& dis(*c,p[0]) > dis(*d,p[0]) ) )
 36                 return 1;
 37         return -1;
 38 }
 39 
 40 inline void tubao(int n,int &top)
 41 {
 42         int i;
 43         top = 2;
 44         stack[0= p[0];
 45         stack[1= p[1];
 46         stack[2= p[2];
 47         for(i=3;i<=n;i++)
 48         {
 49                 while(Mul(stack[top-1],stack[top],p[i])<=0 && top>=2)
 50                         top --;
 51                 top ++;
 52                 stack[top] = p[i];
 53         }
 54 }
 55 
 56 inline double displ( P p, P l0, P l1 ) {
 57         double t = ( (p.x-l0.x)*(l1.x-l0.x) + (p.y-l0.y)*(l1.y-l0.y) ) / ( dis(l0,p) * dis(l0,l1) );
 58         return dis(p,l0) * sqrt( 1 - t * t );
 59 }
 60 
 61 inline double area( P a, P b, P c ) {
 62         return dis(a,b) * displ(c,a,b) / 2;
 63 }
 64 
 65 double solve() {
 66         int i, j, k;
 67         double ans = 0, anstmp;
 68         for ( i = 0; i < top; ++i ) {
 69             for ( j = i + 1; j < top; ++j ) {
 70                 for ( k = j + 1; k < top; ++k ) {
 71                     anstmp = area( stack[ i ], stack[ j ], stack[ k ] );
 72                     if ( anstmp > ans ) {
 73                         ans = anstmp;
 74                     }
 75                 }
 76             }
 77         }
 78         return ans;
 79 }
 80 
 81 int main()
 82 {
 83         int i,tar;
 84         double x,y;
 85         P temp;
 86         while( scanf("%d",&n) == 1) {
 87                 tar = 0;
 88                 x = y = 0x7FFFFFFF;
 89                 for(i=0;i<n;i++)
 90                 {
 91                         scanf("%lf %lf",&p[i].x,&p[i].y);
 92                         if(p[i].x<|| p[i].x==&& p[i].y<y)
 93                         {
 94                                 x = p[i].x;
 95                                 y = p[i].y;
 96                                 tar = i;
 97                         }
 98                 }
 99                 temp = p[tar];
100                 p[tar] = p[0];
101                 p[0= temp;
102                 qsort(p+1,n-1,sizeof(p[0]),cmp);
103                 p[n] = p[0];
104                 tubao(n,top);
105                 printf( "%0.2lf\n", solve() );
106         }
107         return 0;
108 }
109 

posted on 2011-08-11 17:33 coreBugZJ 阅读(232) 评论(0)  编辑 收藏 引用 所属分类: ACMAlgorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理