傳送門：
Walls
題意：
有一堆與 X Y 軸平行的牆，彼此互不交錯，以及一堆小鳥。
小鳥會找一個離他最近的牆撞上去，保證小鳥能夠找到恰好一個最近的牆，求每個牆被幾隻鳥撞到。
思路：
一個掃描線來沿一個軸掃，將牆壁轉換為矩形開始與結束的區間，要能夠詢問初距離一個座標最近的牆在哪。
之後再沿著另一個軸掃一次即可。
這題我偷懶直接用 set 做掉了，需要把小鳥分成 4 個方向來討論。
code:
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
119
120
121
122
123
124
125
126
127
128
129
130
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
int N, M;
const ll inf = 1ll<<60;
struct Wall {
ll x1, y1, x2, y2;
};
struct Bird {
ll x, y;
};
struct Sort {
ll k1, k2, i;
}; // k1=set key k2=sort key i:= (>N =bird), (<0->+N, <N =wall)
vector<Wall> w;
vector<Bird> b;
vector<Sort> s;
vector<ll> dis, tar;
bool c1(const Sort &s1, const Sort &s2) {
return ((s1.k2 == s2.k2) ? s1.i < s2.i : s1.k2 < s2.k2);
}
struct C1 {
bool operator() (const Sort &s1, const Sort &s2) const {
return ((s1.k1 == s2.k1) ? s1.i < s2.i : s1.k1 < s2.k1);
}
};
void fly(bool tag) { // toward small (left, down)
set<Sort, C1> g;
set<Sort, C1> :: iterator it;
for(size_t i=0; i<s.size(); ++i) {
Sort &t = s[i];
if(t.i >= N) { // bird
t.i -= N;
it = g.lower_bound(t);
if((tag && it != g.begin()) || (!tag && it != g.end())){
if(tag) --it;
int d = t.k1 - it->k1;
if(!tag) d = -d;
if(d < dis[t.i]) {
dis[t.i] = d;
tar[t.i] = it -> i;
}
}
}
else if(t.i < 0) { // wall, end
t.i += N;
g.erase(t);
}
else { // wall, start
g.insert(t);
}
}
}
void sol() {
// fly left
for(int i=0; i<N; ++i) {
s[i] = {w[i].x2, w[i].y1, i};
s[N+i] = {w[i].x2, w[i].y2+1, i-N};
}
for(int i=0; i<M; ++i)
s[N*2+i] = {b[i].x, b[i].y, N+i};
sort(s.begin(), s.end(), c1);
fly(1);
// fly down
for(int i=0; i<N; ++i) {
s[i] = {w[i].y2, w[i].x1, i};
s[N+i] = {w[i].y2, w[i].x2+1, i-N};
}
for(int i=0; i<M; ++i)
s[N*2+i] = {b[i].y, b[i].x, N+i};
sort(s.begin(), s.end(), c1);
fly(1);
// fly right
for(int i=0; i<N; ++i) {
s[i] = {w[i].x1, w[i].y1, i};
s[N+i] = {w[i].x1, w[i].y2+1, i-N};
}
for(int i=0; i<M; ++i)
s[N*2+i] = {b[i].x, b[i].y, N+i};
sort(s.begin(), s.end(), c1);
fly(0);
// fly up
for(int i=0; i<N; ++i) {
s[i] = {w[i].y1, w[i].x1, i};
s[N+i] = {w[i].y1, w[i].x2+1, i-N};
}
for(int i=0; i<M; ++i)
s[N*2+i] = {b[i].y, b[i].x, N+i};
sort(s.begin(), s.end(), c1);
fly(0);
vector<int> cnt(N);
for(int i=0; i<M; ++i)
++cnt[tar[i]];
for(int i=0; i<N; ++i)
printf("%d\n", cnt[i]);
}
int main() {
scanf("%d%d", &N, &M);
w.resize(N);
b.resize(M);
dis.resize(M, inf);
tar.resize(M);
s.resize(2*N+M);
for(int i=0; i<N; ++i) {
scanf("%lld%lld%lld%lld", &w[i].x1, &w[i].y1, &w[i].x2, &w[i].y2);
if(w[i].x1 > w[i].x2) swap(w[i].x1, w[i].x2);
if(w[i].y1 > w[i].y2) swap(w[i].y1, w[i].y2);
}
for(int i=0; i<M; ++i)
scanf("%lld%lld", &b[i].x, &b[i].y);
sol();
}