解題區/解題區 - UVa

UVa 13006 - Cake cut

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

兩個人均分一個簡單凸多邊形的蛋糕，蛋糕高度為 2。第一個人 $A$ 選擇一個頂點 $u$，第二個人 $B$ 選擇另一個頂點 $v$，兩點連線後，將蛋糕分成兩塊，最大那一塊會被 $A$ 拿走，小的那一塊會被 $B$ 拿走，請問在各自最佳策略下，盡可能拿到最大塊面積的結果為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
5
0  0
3  0
3  1
2  2
0  1
6
0  1
1  0
2  0
3  1
2  2
0  2
4
-100000000  -100000000
100000000  -100000000
100000000  100000000
-100000000  100000000
4
-99999995  -100000000
100000000  -100000000
100000000  99999995
-100000000  100000000

Sample Output

1
2
3
4
7 2
6 3
40000000000000000 40000000000000000
39999999999999975 39999998000000025

Solution

首先，在最佳策略下，當 $u$ 已經固定，接下來選擇頂點 $v$，$B$ 的決定必然要使最小塊最大化，而對於 $A$ 而言，選擇 $B$ 已經使最小塊最大化的所有方法中，使得最大塊最大化。

明顯地兩塊面積近似一半，由於是凸多邊形，可以根據掃描線的方式推動頂點 $v$，使得 $\overline{uv}$ 切分的面積近似一半，對於簡單多邊形面積計算由行列式計算，但行列式計算時的變數呈現環狀，先把首尾變數提出，維護中行列式中間一大段的計算，最後補足首尾變數來計算面積。

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 <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <set>
#include <limits.h>
#include <algorithm>
using namespace std;
struct Pt {
    long long x, y;
    Pt(long long a = 0, long long b = 0):
    x(a), y(b) {}
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
};
long long cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
long long area2(Pt o, Pt a, Pt b) {
    return llabs(cross(o, a, b));
}
const int MAXN = 262144;
Pt P[MAXN];
int main() {
    int N;
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i < N; i++) {
            scanf("%lld %lld", &P[i].x, &P[i].y);
            P[i+N] = P[i];
        }
        
        long long area = 0;
        for (int i = 2; i < N; i++)
            area += area2(P[0], P[i-1], P[i]);
        
        long long tmp = 0;
        pair<long long, long long> ret(0, 0);
        tmp += P[0].x * P[1].y - P[0].y * P[1].x;
        tmp += P[1].x * P[2].y - P[1].y * P[2].x;
        for (int i = 0, j = 2; i < N; i++) {
            while (1) {
                long long test = tmp + (P[j].x * P[i].y - P[j].y * P[i].x);
                if (llabs(test)*2 >= area)
                    break;
                tmp += P[j].x * P[j+1].y - P[j].y * P[j+1].x;
                j++;
            }
            long long t1, t2, p1, p2;
            t1 = llabs(tmp + (P[j].x * P[i].y - P[j].y * P[i].x));
            t2 = area - t1;
            p1 = llabs(tmp - (P[j-1].x * P[j].y - P[j-1].y * P[j].x)
                           + (P[j-1].x * P[i].y - P[j-1].y * P[i].x));
            p2 = area - p1;
            if (t1 < t2)    swap(t1, t2);
            if (p1 < p2)    swap(p1, p2);
            if (t1 > p1)    t1 = p1, t2 = p2;
            ret = max(ret, make_pair(t1, t2));
            tmp -= P[i].x * P[i+1].y - P[i].y * P[i+1].x;
        }
        printf("%lld %lld\n", ret.first, ret.second);
    }
    return 0;
}