解題區/解題區 - UVa

UVa 13009 - Fence the vegetables fail

contents

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

Problem

給一個平行兩軸的簡單多邊形花圃以及一堆蔬菜的座標，請問有多少蔬菜在柵欄的外部，把那些在外部的蔬菜編號加總後輸出。

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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
4 8
1 2
1 0
5 3
3 4
0 1
6 1
6 4
4 4
4 3
2 3
2 5
0 5
6 12
6 5
1 9
3 6
3 4
2 0
4 4
5 8
5 3
2 3
2 5
4 5
4 7
0 7
0 1
7 1
7 10
0 10
0 8
1 4
1 1
2 0
2 2
0 2
0 0

Sample Output

1
2
3
6
15
0

Solution

判斷一個點是否在簡單多邊形內部可以使用射線法，然而有很多點詢問，單筆詢問複雜度 $\mathcal{O}(N)$，這樣很明顯地會 TLE。

為了加速判斷，採用掃描線算法，依序放入平行 x 軸的線段，掃描過程中離線詢問某點往 y 軸負方向的射線交點個數為何，維護求交點個數可以利用 binary indexed tree 維護前綴和，前綴和相當於射線交點個數。就能在 $\mathcal{O}(N \log N)$ 完成所有詢問。

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <math.h>
using namespace std;
struct Pt {
    int x, y, v;
    Pt(int a = 0, int 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);
    }
    bool operator<(const Pt &a) const {
        if (x != a.x)
            return x < a.x;
        if (y != a.y)
            return y < a.y;
        return false;
    }
};
struct Seg {
    int xl, xr, y;
    Seg(int a = 0, int b = 0, int c = 0):
    xl(a), xr(b), y(c) {}
    bool operator<(const Seg &u) const {
        return xl < u.xl;
    }
};
Pt P[131072], D[131072];
int BIT[262144];
void modify(int x, int val, int L) {
    while (x <= L)
        BIT[x] += val, x += x&(-x);
}
int query(int x) {
    int sum = 0;
    while (x)
        sum += BIT[x], x -= x&(-x);
    return sum;
}
void solve(int N, int M) {
    map<int, int> RX, RY;
    for (int i = 0; i < N; i++)
        RX[P[i].x] = RY[P[i].y] = 0;
    for (int i = 0; i < M; i++)
        RX[D[i].x] = RY[D[i].y] = 0;
    
    int label_x = 0, label_y = 0;
    
    for (auto &x : RX)
        x.second = ++label_x;
    for (auto &y : RY)
        y.second = ++label_y;
    
    memset(BIT, 0, sizeof(BIT));
    
    for (int i = 0; i < N; i++)
        P[i].x = RX[P[i].x], P[i].y = RY[P[i].y];
    for (int i = 0; i < M; i++)
        D[i].x = RX[D[i].x], D[i].y = RY[D[i].y];
    
    vector<Seg> segs;
    for (int i = 0; i < M; i++) {
        if (D[i].y == D[(i+1)%M].y) {
            int xl = min(D[i].x, D[(i+1)%M].x);
            int xr = max(D[i].x, D[(i+1)%M].x);
            segs.push_back(Seg(xl, xr, D[i].y));
        }
    }
    
    long long outer_val = 0;
    sort(P, P+N);
    sort(segs.begin(), segs.end());
    int Pidx = 0;
    set<std::pair<int, int>> PQ;
    for (int i = 0, line_x = 1; line_x <= label_x; line_x++) {
        while (Pidx < N && P[Pidx].x <= line_x) {
            int intersect = query(P[Pidx].y);
            if (intersect%2 == 0)
                outer_val += P[Pidx].v;
            Pidx++;
        }
        while (!PQ.empty() && PQ.begin()->first <= line_x)
            modify(PQ.begin()->second, -1, label_y), PQ.erase(PQ.begin());
        while (i < segs.size() && segs[i].xl == line_x) {
            modify(segs[i].y, 1, label_y);
            PQ.insert(make_pair(segs[i].xr, segs[i].y));
            i++;
        }
    }
    printf("%lld\n", outer_val);
}
int main() {
    int N, M;
    while (scanf("%d %d", &N, &M) == 2) {
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &P[i].x, &P[i].y);
            P[i].v = i+1;
        }
        
        for (int i = 0; i < M; i++)
            scanf("%d %d", &D[i].x, &D[i].y);
        
        solve(N, M);
    }
    return 0;
}