hdu2202（最大三角形）凸包

最大三角形

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3184 Accepted Submission(s): 1075

Problem Description

老师在计算几何这门课上给Eddy布置了一道题目，题目是这样的：给定二维的平面上n个不同的点，要求在这些点里寻找三个点，使他们构成的三角形拥有的面积最大。
Eddy对这道题目百思不得其解，想不通用什么方法来解决，因此他找到了聪明的你，请你帮他解决这个题目。

Input

输入数据包含多组测试用例，每个测试用例的第一行包含一个整数n，表示一共有n个互不相同的点，接下来的n行每行包含2个整数xi,yi，表示平面上第i个点的x与y坐标。你可以认为：3 <= n <= 50000 而且 -10000 <= xi, yi <= 10000.

Output

对于每一组测试数据，请输出构成的最大的三角形的面积，结果保留两位小数。
每组输出占一行。

Sample Input

3 4

2 6

3 7

2 6

3 9

2 0

8 0

6 6

7 7

Sample Output

1.50

27.00

总结：在计算面积时一定要注意三点共线的问题，一时没注意，wa好多次

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<math.h>
 4 #include<algorithm>
 5 using namespace std;
 6 #define N 50010
 7 struct point
 8 {
 9     int x,y;
10     double angel;
11 } p[N],stack[N];
12 int top,n;
13 
14 double dis(point a,point b)
15 {
16     return sqrt(double((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
17 }
18 
19 bool mult(point p1,point p2,point p0)
20 {
21     return (p1.x-p0.x)*(p2.y-p0.y) >= (p2.x-p0.x)*(p1.y-p0.y);
22 }
23 
24 bool cmp(point a,point b)
25 {
26     if(a.angel == b.angel)
27     {
28         if (a.x == b.x)
29             return a.y > b.y;
30         return a.x > b.x;
31     }
32     return a.angel < b.angel;
33 }
34 
35 void graham()
36 {
37     int i,k=0;
38     for(i=0; i<n; i++)
39         if(p[i].y<p[k].y||((p[i].y==p[k].y)&&(p[i].x<p[k].x)))
40             k=i;
41     swap(p[0],p[k]);
42     for(i=1; i<n; i++)
43         p[i].angel=atan2(double(p[i].y-p[0].y),double(p[i].x-p[0].x));
44     sort(p+1,p+n,cmp);
45     stack[0]=p[0];
46     stack[1]=p[1];
47     stack[2]=p[2];
48     top=3;
49     for(i=3; i<n; i++)
50     {
51         while(top > 2 && mult(stack[top-2],stack[top-1],p[i])<=0)
52             top--;
53         stack[top++]=p[i];
54     }
55 }
56 
57 int main()
58 {
59     int i,j,k;
60     double ans,t,s1,s2,s3,max;
61     while(scanf("%d",&n)!=EOF)
62     {
63         for(i=0; i<n; i++)
64             scanf("%d%d",&p[i].x,&p[i].y);
65         graham();
66         ans=0;
67         max=0;
68         for(i=0; i<top-2; i++)
69             for(j=i+1; j<top-1; j++)
70                 for(k=j+1; k<top; k++)
71                 {
72                     if(mult(stack[i],stack[j],stack[k])==0)
73                     continue;
74                     s1=dis(stack[i],stack[j]);
75                     s2=dis(stack[j],stack[k]);
76                     s3=dis(stack[k],stack[i]);
77                     t=(s1+s2+s3)/2;
78                     ans=t*(t-s1)*(t-s2)*(t-s3);
79                     if(ans>max)
80                         max=ans;
81                 }
82         printf("%.2lf
",sqrt(max));
83     }
84     return 0;
85 }

View Code

hdu2202（最大三角形 ）凸包

最大三角形

hdu2202（最大三角形）凸包