hdu 2202 最大三角形 (Convex Hull && (Bruce Force || Rotate Stuck))

　　题目中文，不另外解释。

　　做法是构造出凸包，估计点是随机出的，所以凸包的大小不会太大，于是可以直接对凸包上的点进行暴力计算三角形的面积。

　　如果随机的点是n个，凸包上面有m个点，那么复杂度就是O(n+m^3)。代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 #include <iostream>
 6 
 7 using namespace std;
 8 
 9 const double EPS = 1e-8;
10 inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
11 struct Point {
12     double x, y;
13     Point() {}
14     Point(double x, double y) : x(x), y(y) {}
15     bool operator < (Point a) const { return sgn(x - a.x) < 0 || sgn(x - a.x) == 0 && y < a.y;}
16     bool operator == (Point a) const { return sgn(x - a.x) == 0 && sgn(y - a.y) == 0;}
17     Point operator + (Point a) const { return Point(x + a.x, y + a.y);}
18     Point operator - (Point a) const { return Point(x - a.x, y - a.y);}
19     Point operator * (double p) const { return Point(x * p, y * p);}
20     Point operator / (double p) const { return Point(x / p, y / p);}
21 } ;
22 typedef Point Vec;
23 inline double crossDet(Point a, Point b) { return a.x * b.y - a.y * b.x;}
24 inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
25 inline double dotDet(Point a, Point b) { return a.x * b.x + a.y * b.y;}
26 inline double vecLen(Vec x) { return sqrt(dotDet(x, x));}
27 
28 struct Line {
29     Point s, t;
30     Line() {}
31     Line(Point s, Point t) : s(s), t(t) {}
32     Vec vec() { return t - s;}
33     Point point(double x) { return s + (t - s) * x;}
34 } ;
35 typedef Line Seg;
36 double pt2Line(Point x, Point a, Point b) {
37     Vec v1 = b - a, v2 = x - a;
38     return crossDet(v1, v2) / vecLen(v1);
39 }
40 inline double pt2Line(Point x, Line L) { return pt2Line(x, L.s, L.t);}
41 
42 int andrew(Point *pt, int n, Point *ch) {
43     sort(pt, pt + n);
44     int m = 0;
45     for (int i = 0; i < n; i++) {
46         while (m > 1 && sgn(crossDet(ch[m - 2], ch[m - 1], pt[i])) <= 0) m--;
47         ch[m++] = pt[i];
48     }
49     int k = m;
50     for (int i = n - 2; i >= 0; i--) {
51         while (m > k && sgn(crossDet(ch[m - 2], ch[m - 1], pt[i])) <= 0) m--;
52         ch[m++] = pt[i];
53     }
54     if (n > 1) m--;
55     return m;
56 }
57 
58 const int N = 55555;
59 const double FINF = 1e20;
60 Point pt[N], ch[N];
61 
62 int main() {
63 //    freopen("in", "r", stdin);
64     int n;
65     while (cin >> n) {
66         for (int i = 0; i < n; i++) scanf("%lf%lf", &pt[i].x, &pt[i].y);
67         n = andrew(pt, n, ch);
68 //        for (int i = 0; i < n; i++) {
69 //            cout << ch[i].x << ' ' << ch[i].y << endl;
70 //        }
71         double maxArea = 0.0;
72         for (int i = 0; i < n; i++) {
73             for (int j = i + 1; j < n; j++) {
74                 for (int k = j + 1; k < n; k++) {
75                     maxArea = max(maxArea, fabs(crossDet(ch[i], ch[j], ch[k])) / 2.0);
76                 }
77             }
78         }
79         printf("%.2f\n", maxArea);
80     }
81     return 0;
82 }

View Code

　　还有一种做法，就是O(n+m^2)求对踵点的方法。每次枚举其中一条边，然后扫描求出对踵点，移动一条边的一个端点，同时继续搜索对踵点。这里对于每一条新的边，对踵点都是继续往下一个点移动。这样子，对于每个确定的端点都是只需要访问O(m)个对踵点。这样的操作共有m次，所以这里的复杂度是O(m^2)。代码如下：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <algorithm>
  5 #include <iostream>
  6 
  7 using namespace std;
  8 
  9 const double EPS = 1e-8;
 10 inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
 11 struct Point {
 12     double x, y;
 13     Point() {}
 14     Point(double x, double y) : x(x), y(y) {}
 15     bool operator < (Point a) const { return sgn(x - a.x) < 0 || sgn(x - a.x) == 0 && y < a.y;}
 16     bool operator == (Point a) const { return sgn(x - a.x) == 0 && sgn(y - a.y) == 0;}
 17     Point operator + (Point a) const { return Point(x + a.x, y + a.y);}
 18     Point operator - (Point a) const { return Point(x - a.x, y - a.y);}
 19     Point operator * (double p) const { return Point(x * p, y * p);}
 20     Point operator / (double p) const { return Point(x / p, y / p);}
 21 } ;
 22 typedef Point Vec;
 23 inline double crossDet(Point a, Point b) { return a.x * b.y - a.y * b.x;}
 24 inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
 25 inline double dotDet(Point a, Point b) { return a.x * b.x + a.y * b.y;}
 26 inline double vecLen(Vec x) { return sqrt(dotDet(x, x));}
 27 
 28 struct Line {
 29     Point s, t;
 30     Line() {}
 31     Line(Point s, Point t) : s(s), t(t) {}
 32     Vec vec() { return t - s;}
 33     Point point(double x) { return s + (t - s) * x;}
 34 } ;
 35 typedef Line Seg;
 36 double pt2Line(Point x, Point a, Point b) {
 37     Vec v1 = b - a, v2 = x - a;
 38     return crossDet(v1, v2) / vecLen(v1);
 39 }
 40 inline double pt2Line(Point x, Line L) { return pt2Line(x, L.s, L.t);}
 41 
 42 int andrew(Point *pt, int n, Point *ch) {
 43     sort(pt, pt + n);
 44     int m = 0;
 45     for (int i = 0; i < n; i++) {
 46         while (m > 1 && sgn(crossDet(ch[m - 2], ch[m - 1], pt[i])) <= 0) m--;
 47         ch[m++] = pt[i];
 48     }
 49     int k = m;
 50     for (int i = n - 2; i >= 0; i--) {
 51         while (m > k && sgn(crossDet(ch[m - 2], ch[m - 1], pt[i])) <= 0) m--;
 52         ch[m++] = pt[i];
 53     }
 54     if (n > 1) m--;
 55     return m;
 56 }
 57 
 58 const int N = 55555;
 59 const double FINF = 1e20;
 60 Point pt[N], ch[N];
 61 
 62 int main() {
 63 //    freopen("in", "r", stdin);
 64     int n;
 65     while (cin >> n) {
 66         for (int i = 0; i < n; i++) scanf("%lf%lf", &pt[i].x, &pt[i].y);
 67         n = andrew(pt, n, ch);
 68         ch[n] = ch[0];
 69 //        for (int i = 0; i < n; i++) {
 70 //            cout << ch[i].x << ' ' << ch[i].y << endl;
 71 //        }
 72         double maxArea = 0.0;
 73         for (int i = 0; i < n; i++) {
 74             int mk = i;
 75             double last = 0.0, cur = fabs(pt2Line(ch[mk], ch[i], ch[i + 1]));
 76             while (true) {
 77                 if (sgn(last - cur) > 0) break;
 78                 last = cur;
 79                 mk = (mk + 1) % n;
 80                 cur = pt2Line(ch[mk], ch[i], ch[i + 1]);
 81             }
 82             mk = (mk + n - 1) % n;
 83             maxArea = max(maxArea, fabs(crossDet(ch[mk], ch[i], ch[i + 1])) / 2.0);
 84             for (int j = 2; j < n - 1; j++) {
 85                 int k = (i + j) % n;
 86                 last = 0.0, cur = fabs(pt2Line(ch[mk], ch[i], ch[k]));
 87                 while (true) {
 88                     if (sgn(last - cur) > 0) break;
 89                     last = cur;
 90                     mk = (mk + 1) % n;
 91                     cur = pt2Line(ch[mk], ch[i], ch[k]);
 92                 }
 93                 mk = (mk + n - 1) % n;
 94                 maxArea = max(maxArea, fabs(crossDet(ch[mk], ch[i], ch[k])) / 2.0);
 95             }
 96         }
 97         printf("%.2f\n", maxArea);
 98     }
 99     return 0;
100 }

View Code

　　对于最特殊的情况，也就是有50000个点在凸包上的算法暂时没有想到。

——written by Lyon