解題區/解題區 - Zerojudge

b321. 河道分界

contents

  1. 1. 內容 ：
  2. 2. 輸入說明 ：
  3. 3. 輸出說明 ：
  4. 4. 範例輸入 ：
  5. 5. 範例輸出 ：
  6. 6. Solution

內容 ：

M 國開始藉由河道進行分裂，M 國土只會介於 y = 0 和 y = 1 之間，在 x 軸兩側無限延伸，保證河道彼此不會相交任何一點。

操作 A u v : 增加河道 (u, 1) 到 (v, 0)，該河道編號為當前操作 A 的數量。

操作 Q x y : 詢問位置 (x, y) 在哪兩個河道之間。

輸入說明 ：

第一行將會有一個整數 N (N < 100, 000)，表示接下來會有幾筆操作。

操作 A u v : u, v [-50000, 50000] 之間的實數。

操作 Q x y : x 屬於 [-50000, 50000], y 屬於 [0, 1]。

輸出說明 ：

對於每個詢問，輸出在哪兩個河道之間，邊界為 [S, M]，如果恰好在河道上輸出 [?, ?]，詳細請參考範例輸出。

範例輸入 ：

1
2
3
4
5
6
7
8
9
8
A 0 0
Q -1 0
Q 1 0
Q 0 0
A 1 2
Q 1 0.5
Q 3 0.5
Q 1.5 0.5

範例輸出 ：

1
2
3
4
5
6
[S, 1]
[1, M]
[?, ?]
[1, 2]
[2, M]
[?, ?]

Solution

建造一個 BST，這裡使用內建 std::set 的紅黑樹，查找 lower_bound 即可。如果是靜態的河道，一開始對其排序即可，然後二分查找 lower_bound。

如果測資有錯，歡迎打我。

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct seg {
    Pt s, e;
    int label;
    seg(Pt a, Pt b):s(a), e(b) {}
};
struct CMP {
    static double y;
    
    double interpolate(const Pt& p1, const Pt& p2, double& y) {
        if (p1.y == p2.y) return p1.x;
        return p1.x + (double)(p2.x - p1.x) / (p2.y - p1.y) * (y - p1.y);
    }
    
    bool operator()(const seg &i, const seg &j) {
        double v1 = interpolate(i.s, i.e, y), v2 = interpolate(j.s, j.e, y);
        if (fabs(v1 - v2) > eps)
            return v1 < v2;
        return false;
    }
};
double CMP::y = 0;
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
    int n;
    double x, y, up, down;
    char cmd[10];
    while (scanf("%d", &n) == 1) {
        set<seg, CMP> S;
        for (int i = 0, k = 1; i < n; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'A') {
                scanf("%lf %lf", &up, &down);
                seg tmp = seg(Pt(up, 1), Pt(down, 0));
                tmp.label = k;
                S.insert(tmp), k++;
            } else {
                scanf("%lf %lf", &x, &y);
                CMP::y = y;
                set<seg>::iterator it = S.lower_bound(seg(Pt(x, 1), Pt(x, 1))), jt;
                if (it != S.end()) {
                    if (onSeg(it->s, it->e, Pt(x, y))) {
                        puts("[?, ?]");
                        continue;
                    }
                }
                int l = -1, r = -1;
                if (it != S.begin()) {
                    jt = it, jt--;
                    l = jt->label;
                    if (onSeg(jt->s, jt->e, Pt(x, y))) {
                        puts("[?, ?]");
                        continue;
                    }
                }
                if (it != S.end())
                    r = it->label;
                if (l == -1)
                    printf("[S, ");
                else
                    printf("[%d, ", l);
                if (r == -1)
                    printf("M]");
                else
                    printf("%d]", r);
                puts("");
            }
        }
    }
    return 0;
}