백준17973 Quadrilaterals

작성일 | In

문제 링크

  • http://icpc.me/17973

문제 출처

  • 2019 서울 리저널 F번

사용 알고리즘

  • Rotating Sweep Line

시간복잡도

  • $O(N^2 \log N)$

풀이

N개의 점으로 만들 수 있는 모든 사각형 중

  • 볼록 다각형이면서 넓이가 $\alpha$이면 4점
  • 오목 다각형이면서 넓이가 $\alpha$이면 3점
  • 볼록 다각형이면서 넓이가 $\alpha$가 아니면 2점
  • 오목 다각형이면서 넓이가 $\alpha$가 아니면 1점

을 얻는다고 했을 때, 총점을 구하는 문제입니다. 이때 $\alpha$는 만들 수 있는 사각형의 넓이 중 최솟값입니다.

점수 계산 방식을 아래처럼 바꿀 수 있습니다.

  • 볼록 다각형이면 2점
  • 오목 다각형이면 1점
  • 넓이가 $\alpha$면 2점 추가

볼록사각형은 대각선이 2개, 오목사각형은 대각선이 1개이므로 이렇게 바꿔줄 수도 있습니다.

  • 대각선 하나당 1점
  • 넓이가 $\alpha$인 사각형 하나당 2점

이제 우리는 대각선의 개수를 구하는 문제와 만들 수 있는 사각형의 최소 넓이를 구하는 문제를 풀면 됩니다.

대각선의 개수

사각형에 사용할 두 점을 고정시켜봅시다.

두 점을 잇는 선분을 대각선으로 하는 사각형의 개수는 빨간선을 기준으로 나누어진 반평면에 속한 점의 개수의 곱입니다.

대각선의 개수를 구하기 위해서 두 점을 고정하는 $n(n-1)/2$가지의 경우마다 어떤 점이 어떤 반평면에 속하는지 알아야 합니다.
두 점 a, b을 잇는 선분에 수직인 직선을 그려서, 모든 점을 그 직선에 사영시켜봅시다.

사영시킨 다음 좌표를 기준으로 정렬하면, a 혹은 b를 기준으로 두 반평면이 구분됩니다.

$n(n-1)/2$가지의 경우에 대해 모두 사영시킨 결과의 순서를 빠르게 계산할 수 있다면 대각선의 개수도 빠르게 구할 수 있습니다.

$n(n-1)/2$개의 선분을 기울기 순으로 정렬하고 순서대로 보면, 각 선분을 전후로 inversion이 발생하는 점의 쌍은 하나밖에 없고, 이 두 점은 인접하면서 그러한 두 점은 해당 선분이 잇는 두 점입니다.
그러므로 우리는 $O(N^2)$ 만에 모든 순서를 다 알아낼 수 있고, 대각선의 개수도 $O(N^2)$에 구할 수 있습니다.

최소 넓이

이번에도 두 점을 고정시킨 다음 두 점을 잇는 선분과 수직인 직선에 사영을 하고 시작합시다.

이렇게 사영시켰을 때 고정시킨 두 점의 순서를 각각 a, b라고 합시다. (a < b)
당연히 b - a = 1입니다.

고정시킨 두 점을 이용하면서 최소 넓이 사각형이 될 수 있는 후보는

  • a-2번째, a번째, b번째, b+1번째 점으로 만든 사각형
  • a-1번째, a번째, b번째, b+1번째 점으로 만든 사각형
  • a-2번째, a번째, b번째, b+2번째 점으로 만든 사각형
  • a-1번째, a번째, b번째, b+2번째 점으로 만든 사각형

총 4가지입니다.

a-2, a-1, a, b를 이용하는 경우 같은 건 다른 선분에 대해 처리할 때 고려하기 때문에 생각할 필요가 없습니다.
각 선분마다 사각형 4개를 보면서 최소 넓이와 개수를 카운팅하면 문제를 풀 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define int long long
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n;
p v[1010];

ll ccw(const p &a, const p &b, const p &c){
    ll dx1 = b.x - a.x, dy1 = b.y - a.y;
    ll dx2 = c.x - b.x, dy2 = c.y - b.y;
    return dx1*dy2 - dx2*dy1;
}

ll area(const p &a, const p &b, const p &c){
    return abs(ccw(a, b, c));
}

struct Line{
    ll i, j, dx, dy;
    Line(int i, int j) : i(i), j(j) {
        dx = v[i].x - v[j].x;
        dy = v[i].y - v[j].y;
        if(dx < 0) dx *= -1, dy *= -1;
    }
    bool operator < (const Line &t) const {
        return dy * t.dx < t.dy * dx;
    }
};
vector<Line> line;
int idx[1010];

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> v[i].x >> v[i].y;
    sort(v+1, v+n+1);
    for(int i=1; i<=n; i++) idx[i] = i;
    for(int i=1; i<=n; i++) for(int j=1; j<i; j++) line.emplace_back(i, j);
    sort(all(line));

    int j;
    ll mn = 9e18;
    ll dia = 0, same = 0;
    for(auto i : line){
        int a = i.i, b = i.j;
        swap(v[idx[a]], v[idx[b]]); swap(idx[a], idx[b]);
        a = idx[a], b = idx[b];
        if(a > b) swap(a, b);
        assert(b-a == 1);
        dia += 1LL * (a-1) * (n-b);

        for(int x=max<ll>(1, a-3); x<a; x++) for(int y=b+1; y<=min<ll>(b+3, n); y++){
                ll now = area(v[x], v[a], v[b]) + area(v[y], v[a], v[b]);
                if(mn > now) mn = now, same = 0;
                if(mn == now){
                    same++;
                    if((ccw(v[x], v[y], v[a]) > 0) == (ccw(v[x], v[y], v[b]) > 0)) same++;
                }
            }
    }

    // cout << dia << " " << same << " " << mn << "\n";
    cout << dia + same;
}