• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 閱讀(252) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm

            欧美性大战久久久久久| 超级97碰碰碰碰久久久久最新| av国内精品久久久久影院| 久久精品国产第一区二区三区| MM131亚洲国产美女久久| 久久99国产一区二区三区| 精品久久久一二三区| 精品国产福利久久久| 亚洲精品国精品久久99热| 久久久国产精品亚洲一区| 国产午夜福利精品久久| 亚洲成色www久久网站夜月| 国产精品久久国产精品99盘| 亚洲欧洲久久久精品| 欧美精品一本久久男人的天堂| 一级A毛片免费观看久久精品| 久久综合丝袜日本网| 亚洲AV无码久久精品蜜桃| 青青青青久久精品国产h久久精品五福影院1421| 久久亚洲国产精品成人AV秋霞| 国内精品久久久久久久久电影网| 久久久噜噜噜久久中文字幕色伊伊| 亚洲午夜久久影院| 99久久精品日本一区二区免费| 99久久综合国产精品免费| 久久综合色区| 久久久久国色AV免费观看| 久久国产成人精品麻豆| 国产精品无码久久综合| 无码国产69精品久久久久网站| 久久99国产精品久久99小说| 欧美日韩精品久久久免费观看 | 伊人情人综合成人久久网小说| 99re这里只有精品热久久| 久久综合精品国产二区无码| 久久婷婷五月综合色奶水99啪| 色综合久久天天综线观看| 久久亚洲AV无码西西人体| 色综合合久久天天给综看| 亚洲国产精品狼友中文久久久| 亚洲第一永久AV网站久久精品男人的天堂AV |