HDOJ 2202

发表于 |

题目

二维平面上，给$N$个整点（坐标都是整数）。求以这些点为顶点的最大三角形面积。

数据范围

$3\leq N \leq 50000 \quad |坐标|\leq 10000$

做法

旋转卡壳

PS:有个性质：整点，坐标范围为$M$的凸多边形顶点数只有$O(\sqrt M)$个。

由于坐标范围是10000，所以凸包上最多100个点。直接在凸包上暴力也行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 50005;
struct point
{
  ll x, y;
  point() {}
  point(ll _x, ll _y) : x(_x), y(_y) {}
  point operator - (const point &b) const
  {
    return point(x - b.x, y - b.y);
  }
  ll operator ^ (const point &b) const
  {
    return x * b.y - b.x * y;
  }
  ll operator * (const point &b) const
  {
    return x * b.x + y * b.y;
  }
};
int N;
point p[MAX_N], pch[MAX_N];
point A, B, C;
bool cmp_xy(const point &a, const point &b)
{
  if (a.x == b.x) return a.y < b.y;
  return a.x < b.x;
}
int ConvexHull(point pnt[], int n, point res[])
{
  sort(pnt, pnt + n, cmp_xy);
  int k = 0;
  for (int i = 0; i < n; ++i) {
    while (k > 1 && ((res[k - 1] - res[k - 2]) ^ (pnt[i] - res[k - 1])) <= 0) k--;
    res[k++] = pnt[i];
  }
  for (int i = n - 2, t = k; i >= 0; --i) {
    while (k > t && ((res[k - 1] - res[k - 2]) ^ (pnt[i] - res[k - 1])) <= 0) k--;
    res[k++] = pnt[i];
  }
  return k - 1;
}
inline ll GetArea2(const point &a, const point &b, const point &c)
{
  return abs((a - b) ^ (a - c));
}
ll MaxArea(point pnt[], int n)
{
  A = pnt[0]; B = pnt[1]; C = pnt[2];
  ll max_area = GetArea2(A, B, C);
  for (int i = 0; i < n; ++i) {
    int cur = i + 1;
    for (int j = i + 1; j < n; ++j) {
      cur = max(cur, j + 1);
      while (cur + 1 < n && GetArea2(pnt[i], pnt[j], pnt[cur + 1]) > GetArea2(pnt[i], pnt[j], pnt[cur])) cur++;
      ll tmp_area = GetArea2(pnt[i], pnt[j], pnt[cur]);
      if (max_area < tmp_area) {
        max_area = tmp_area;
        A = pnt[i];
        B = pnt[j];
        C = pnt[cur];
      }
    }
  }
  return max_area;
}
int main()
{
  while (scanf("%d", &N) != EOF) {
    for (int i = 0; i < N; ++i) {
      scanf("%lld%lld", &p[i].x, &p[i].y);
    }
    int nch = ConvexHull(p, N, pch);
    if (nch < 3) {
      printf("0.00\n");
    } else {
      printf("%.2f\n", (double)MaxArea(pch, nch) / 2);
    }
  }
  return 0;
}