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