Codeforces 682E

发表于 |

题目

二维平面上，给$N$个整点（坐标都是整数），保证以这些点为顶点的三角形的面积不超过$S$。让你找出一个整点三角形（顶点不一定是给出的点），包含所有给出的点，且面积不超过$4S$。

数据范围

$3\leq N \leq 5000 \quad |坐标|\leq 10^8$

做法

给出的点组成的最大的三角形的顶点记为$a,b,c$，面积记为$s$。用反证法，易证：以$a,b,c$为三边中点的三角形包含所有给出的点，记其面积为$S_{max}$。显然，上述两个三角形相似。所以:$4S\geq 4s = S_{max}$ 。故，上述两个三角形的后者即为所求。

而最大的三角形可以用旋转卡壳法求出，复杂度为$O(N^2)$。

代码

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
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 5005;
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()
{
  ll S;
  scanf("%d%lld", &N, &S);
  for (int i = 0; i < N; ++i) {
    scanf("%lld%lld", &p[i].x, &p[i].y);
  }
  int nch = ConvexHull(p, N, pch);
  MaxArea(pch, nch);
  printf("%lld %lld\n", A.x + B.x - C.x, A.y + B.y - C.y);
  printf("%lld %lld\n", B.x + C.x - A.x, B.y + C.y - A.y);
  printf("%lld %lld\n", C.x + A.x - B.x, C.y + A.y - B.y);
  return 0;
}