UVa 1398 - Meteor

contents

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

Problem

進行天文觀測,天空上有 n 個流星,以及拍攝的區域。

給定每一個流星的起始位置與速度,請問在哪一個時刻可以拍到最多顆流星在拍攝區域內部。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
4 2
2
-1 1 1 -1
5 2 -1 -1
13 6
7
3 -2 1 3
6 9 -2 -1
8 0 -1 -1
7 6 10 0
11 -2 2 1
-2 4 6 -1
3 2 -5 -1

Sample Output

1
2
1
2

Solution

將每一個流星進入和離開拍攝區域的時間求出,並且組合成 (enter_time, 1), (leave_time, -1) 的方式,根據時間由小排到大,利用掃描線算法統計累計的最大值即可。

求流星進出區域的時間,可以將 x, y 座標分開考慮,對進入時間取最大值、離開時間取最小值。

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
// sweep line algorithm
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int LCM = 2520; // gcd(1, 2, 3, ..., 10) = 2520, /vx, /vy, vx, vy <= 10
int W, H;
pair<int, int> getTime(int sx, int sy, int vx, int vy) {
int enter = 0, leave = INF;
if (vx == 0) {
if (sx <= 0 || sx >= W)
leave = 0;
} else if (vx < 0) {
enter = max(enter, (sx - W) * LCM / (-vx));
leave = min(leave, (sx - 0) * LCM / (-vx));
} else {
enter = max(enter, (0 - sx) * LCM / (vx));
leave = min(leave, (W - sx) * LCM / (vx));
}
if (vy == 0) {
if (sy <= 0 || sy >= H)
leave = 0;
} else if (vy < 0) {
enter = max(enter, (sy - H) * LCM / (-vy));
leave = min(leave, (sy - 0) * LCM / (-vy));
} else {
enter = max(enter, (0 - sy) * LCM / (vy));
leave = min(leave, (H - sy) * LCM / (vy));
}
return make_pair(enter, leave);
}
int main() {
int testcase, N;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d", &W, &H);
scanf("%d", &N);
vector< pair<int, int> > D;
for (int i = 0; i < N; i++) {
int sx, sy, vx, vy;
scanf("%d %d %d %d", &sx, &sy, &vx, &vy);
pair<int, int> t = getTime(sx, sy, vx, vy);
if (t.first < t.second) {
D.push_back(make_pair(t.first, 1));
D.push_back(make_pair(t.second, -1));
}
}
sort(D.begin(), D.end());
int ret = 0;
for (int i = 0, s = 0; i < D.size(); i++) {
s += D[i].second;
ret = max(ret, s);
}
printf("%d\n", ret);
}
return 0;
}