• <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无码精品麻豆 | 精品久久8x国产免费观看| 99久久99久久精品国产| 欧美伊人久久大香线蕉综合 | 色婷婷久久综合中文久久蜜桃av| 国产精品久久久久久久| 欧洲国产伦久久久久久久| 亚洲人成网亚洲欧洲无码久久| 久久精品成人免费网站| 狠狠色丁香久久婷婷综合_中| 久久精品国产半推半就| 久久精品国产欧美日韩99热| 欧美久久精品一级c片片| 2021国产精品久久精品| 国产精品VIDEOSSEX久久发布| 奇米影视7777久久精品人人爽| 伊人久久综合热线大杳蕉下载| 亚洲精品蜜桃久久久久久| 久久久人妻精品无码一区| 欧美亚洲另类久久综合| 久久久久亚洲AV无码麻豆| 久久精品国产亚洲AV久| 色诱久久av| 久久无码一区二区三区少妇 | 久久国产精品免费一区| 国产精品久久网| 久久亚洲精品国产精品| 亚洲人成精品久久久久| 亚洲愉拍99热成人精品热久久| 久久99热这里只频精品6| 久久男人中文字幕资源站| 精品国产婷婷久久久| 久久精品视频91| 日本国产精品久久| 亚洲精品国精品久久99热| 伊人久久大香线蕉成人| 中文字幕无码精品亚洲资源网久久| 亚洲色欲久久久久综合网| 思思久久99热只有频精品66|