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

            精品伊人久久久| 精品视频久久久久| 精品久久久噜噜噜久久久| 狠狠88综合久久久久综合网| 伊人久久综合热线大杳蕉下载| 久久精品亚洲乱码伦伦中文| 久久久久亚洲av成人网人人软件| 久久精品国产亚洲欧美| 中文字幕亚洲综合久久菠萝蜜| 亚洲av伊人久久综合密臀性色| 9999国产精品欧美久久久久久| 99精品久久久久久久婷婷| 国产精品女同一区二区久久| 无码日韩人妻精品久久蜜桃 | 污污内射久久一区二区欧美日韩| 亚洲国产精品无码久久一区二区| 精品免费久久久久国产一区| 久久婷婷综合中文字幕| 熟妇人妻久久中文字幕| 久久只有这精品99| 精品久久国产一区二区三区香蕉| 精品久久久久久综合日本| 日韩人妻无码精品久久免费一 | 久久夜色精品国产噜噜亚洲a | 精品免费tv久久久久久久| 99久久精品国产一区二区| 久久婷婷国产剧情内射白浆| 无夜精品久久久久久| 久久香蕉国产线看观看猫咪?v| 国产精品美女久久久久AV福利| 久久久久久综合一区中文字幕 | 国产福利电影一区二区三区久久久久成人精品综合 | 久久WWW免费人成一看片| 亚洲国产一成久久精品国产成人综合 | 性做久久久久久久久| 久久久久久亚洲精品无码| 国产巨作麻豆欧美亚洲综合久久| 免费国产99久久久香蕉| 久久精品无码av| 久久无码中文字幕东京热| 无码人妻久久一区二区三区|