• <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

            久久午夜电影网| 热久久国产欧美一区二区精品| 伊人久久大香线蕉av一区| 亚洲午夜久久久久妓女影院| 人妻少妇久久中文字幕| 国内精品久久久久久99蜜桃| 国产综合成人久久大片91| 日本久久中文字幕| 久久99国产综合精品女同| 久久e热在这里只有国产中文精品99 | 日本久久久久亚洲中字幕 | 嫩草影院久久99| 久久毛片一区二区| 久久福利青草精品资源站免费| 性高朝久久久久久久久久| 久久久久人妻一区精品色| 久久se精品一区二区影院 | 国产精品久久久久9999| 人人狠狠综合久久亚洲高清| jizzjizz国产精品久久| 久久久久久久精品成人热色戒| 国产精品久久久久乳精品爆| 色综合久久久久综合体桃花网| 无码乱码观看精品久久| 亚洲国产成人久久综合碰碰动漫3d| 尹人香蕉久久99天天拍| 久久久久国产| 久久精品中文字幕第23页| 一级做a爰片久久毛片人呢| AV无码久久久久不卡蜜桃| 丁香色欲久久久久久综合网| 亚洲欧美日韩久久精品| 欧洲性大片xxxxx久久久| 国产精品免费久久| 精品久久久久久国产牛牛app| 93精91精品国产综合久久香蕉| 国产精品99久久久久久人| 无码国内精品久久人妻蜜桃| 亚洲色大成网站www久久九| 精品无码久久久久国产动漫3d| 狠狠精品久久久无码中文字幕|