1193 - Radar Installation

[waleed.lutfi]

Please can any one give me some critical input, I got WA for this one I don't know why!

[brianfry713]

Input:

Code: Select all

16 56
-43 20
-7 16
12 29
-5 14
36 12
48 17
0 51
2 24
37 31
-19 18
0 2
29 9
21 28
-8 53
28 1
-23 12

7 14
1 2
35 14
18 8
34 2
-14 7
-31 12
8 6

20 16
-7 5
-15 6
-26 2
-32 17
-41 12
18 10
32 12
-38 17
13 10
33 8
19 8
0 13
-44 6
-1 5
-17 17
3 4
-18 5
1 17
1 6
25 13

2 18
0 6
29 1

15 86
-39 61
28 62
39 62
-13 64
5 48
-39 27
-45 33
-34 34
6 56
48 1
-9 66
23 16
20 60
-38 37
39 20

19 95
-30 53
31 95
-43 6
-42 15
-41 95
-48 72
37 27
-46 35
-12 56
5 39
-22 33
41 5
5 95
1 72
4 85
47 60
23 7
37 55
-50 5

16 94
16 56
26 7
16 19
-2 48
37 38
39 42
-14 46
16 78
38 13
38 60
-34 88
18 56
-35 57
23 66
-48 47
28 75

1 15
23 15

15 91
41 78
31 11
-5 29
14 83
12 72
-17 89
44 7
38 62
-7 87
-29 60
21 53
38 52
-7 50
-42 28
39 33

20 94
27 73
14 26
-5 10
-12 90
31 80
12 24
-26 29
-8 16
3 55
-10 15
-11 63
-24 44
-15 4
-47 52
35 33
-41 83
-25 50
-9 5
-47 8
32 45

17 54
14 10
-4 14
48 3
-27 50
26 54
-32 8
47 6
43 31
32 47
0 2
-5 15
20 8
0 39
19 4
-41 50
-22 9
-48 42

15 33
-25 5
-8 1
-32 15
11 33
19 27
19 1
-13 29
-2 10
49 16
23 7
-7 6
-17 16
16 13
-20 10
-11 5

4 24
21 17
-28 17
-20 18
-40 9

1 90
-46 29

8 2
12 2
20 3
-48 3
-19 3
-33 2
2 2
20 2
13 2

15 60
-37 60
-21 60
16 12
45 30
-28 15
37 35
-47 51
28 39
40 60
40 47
-30 6
20 34
-42 55
-34 10
37 46

17 62
8 41
45 8
-16 3
-14 57
44 2
35 33
-24 10
25 3
-3 42
-13 30
24 50
42 59
-50 52
-41 16
-14 17
-11 14
-35 51

7 23
-21 23
8 20
33 1
-24 16
-40 6
27 18
17 3

15 77
-24 76
29 26
-21 51
15 32
-37 22
10 55
44 31
-20 26
44 63
2 76
-14 19
-11 59
29 34
7 28
33 12

15 40
-46 27
37 37
11 4
1 35
10 6
4 41
48 13
-19 33
28 38
-28 38
-37 10
-37 37
-19 27
41 26
7 37

0 0

AC output:

Code: Select all

Case 1: 1
Case 2: 3
Case 3: -1
Case 4: 1
Case 5: 1
Case 6: 3
Case 7: 1
Case 8: 1
Case 9: 1
Case 10: 1
Case 11: 2
Case 12: 3
Case 13: 2
Case 14: 1
Case 15: -1
Case 16: 3
Case 17: 2
Case 18: 2
Case 19: 2
Case 20: -1

[waleed.lutfi]

Thanks, I found some mistakes and fixed them, but now I'm getting RTE!!
Here is my code, any help is appreciated

Code: Select all

/* 
 * File:   main.cpp
 * Author: waleed
 *
 * Created on March 20, 2013, 1:58 PM
 */

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for( int i = (a); i < (b); i++ )
#define Fors(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fore(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Set(a, s) memset(a, s, sizeof (a))
#define Read(r) freopen(r, "r", stdin)
#define Write(w) freopen(w, "w", stdout)

using namespace std;

struct Island {
    double x, y;

    bool operator<(const Island & i)const {
        return x < i.x || (x == i.x && y <= i.y);
    }
};
int n, d;

bool dist(Island a, int x) {
    return (sqrt((a.x - x)*(a.x - x) + a.y * a.y)) <= d;
}

int main(int argc, char** argv) {
    int cs(1);
    while (scanf("%d %d", &n, &d) == 2) {
        if (!n && !d) break;
        Island isl[1005];
        bool failed = false;
        for (int i = 0; i < n; i++) {
            cin >> isl[i].x >> isl[i].y;
            if (isl[i].y > d) {
                failed = true;
            }
        }
        if (failed) {
            printf("Case %d: -1\n", cs++);
            continue;
        }
        sort(&isl[0], &isl[n]);
        bool covered[1005];
        int lcov[1005];
        lcov[0] = 0;
        covered[0] = true;
        int l = 1;
        int res = 1;
        double rx = isl[0].x + sqrt(d * d - isl[0].y * isl[0].y);

        Set(covered, false);
        for (int i = 1; i < n && !failed; i++) {
            if (!covered[i]) {
                if (dist(isl[i], rx)) {
                    lcov[l++] = i;
                    covered[i] = true;
                    continue;
                }
                bool done = true;

                rx = isl[i].x - sqrt(d * d - isl[i].y * isl[i].y);
                for (int j = 0; j < l; j++) {
                    if (!dist(isl[lcov[j]], rx)) {
                        done = false;
                        break;
                    }
                }
                if (done) {
                    int j;
                    for (j = i; j < n; j++) {
                        if (dist(isl[j], rx)) {
                            covered[j] = true;
                            lcov[l++] = j;
                        }
                    }
                }

                if (!done) {
                    res++;
                    rx = isl[i].x + sqrt(d * d - isl[i].y * isl[i].y);
                    int j;
                    for (j = i, l = 0; j < n; j++) {
                        if (dist(isl[j], rx)) {
                            covered[j] = true;
                            lcov[l++] = j;
                        }
                    }
                }
            }
        }
        printf("Case %d: %d\n", cs++, res);
    }
    return 0;
}

[brianfry713]

Try keeping the island coordinates as integers until you need to convert them to doubles.

Input:

Code: Select all

1 46
-1 7

4 89
22 45
-44 75
-15 36
-31 70

4 56
17 2
17 50
33 51
-39 15

2 33
-10 32
17 8

11 65
-42 43
-49 36
31 38
-6 48
20 32
49 36
24 28
35 60
15 37
-39 50
34 30

4 70
-18 14
-16 67
3 20
-32 31

2 19
-40 20
-6 13

7 91
40 35
5 59
-1 61
-40 49
47 24
14 3
-5 86

7 2
-2 1
31 3
-9 3
-36 3
20 2
14 3
-15 1

8 32
0 16
40 28
-18 5
-36 6
24 27
13 17
-34 32
-49 6

6 6
-32 1
-16 1
-39 4
-36 6
-27 1
-15 5

8 75
49 18
-14 18
-33 60
-38 4
-17 21
13 4
-5 19
-31 41

4 99
-47 90
-24 34
-13 15
-8 41

13 90
22 60
16 57
32 32
-48 37
-45 38
45 75
-4 9
-5 13
-23 25
-4 19
-45 82
9 58
18 41

10 24
11 13
41 15
-19 11
6 8
9 14
-33 11
27 18
10 13
-27 24
16 6

12 21
27 1
16 19
12 6
-12 17
-2 16
-49 4
-13 12
46 12
48 4
-46 6
26 14
-22 10

17 8
43 4
4 7
40 5
-5 2
23 8
44 2
-4 7
-36 9
-17 1
-17 2
47 6
-9 7
49 4
-12 1
-44 2
32 4
22 9

10 18
-25 1
-27 3
24 7
11 10
-34 10
23 1
-19 6
33 15
-9 2
-17 3

13 93
-27 44
19 18
1 41
-3 74
5 50
-14 47
-28 53
2 23
33 86
-36 3
19 89
-36 86
-25 15

9 80
-50 56
-17 56
-25 43
-16 79
45 53
47 6
-45 15
35 80
46 1

0 0

AC output:

Code: Select all

Case 1: 1
Case 2: 1
Case 3: 1
Case 4: 1
Case 5: 2
Case 6: 1
Case 7: -1
Case 8: 1
Case 9: -1
Case 10: 2
Case 11: 3
Case 12: 1
Case 13: 1
Case 14: 2
Case 15: 2
Case 16: 4
Case 17: -1
Case 18: 2
Case 19: 1
Case 20: 2