解題區/解題區 - UVa

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