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 || (!k && 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<x || p[i].x==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