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;
}