Logo Wy Online Judge

WyOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#448#74. 「NOIP2016」愤怒的小鸟Pigsyy10041ms3612kbC++233.7kb2025-04-24 13:41:182025-04-24 13:41:18

answer

#include <bits/stdc++.h>
using namespace std;
double a[20][20], b[20][20], x[20], y[20], re[20], ida, idb;
bool f[20];

int main() {
    int T, n, m, cnt, cnt1, ans, num, id, id1;
    cin >> T;

    while (T--) {
        cnt1 = 0;
        ans = 0;
        memset(f, 0, sizeof(f));
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(re, 0, sizeof(re));
        memset(x, 0, sizeof(x));
        memset(y, 0, sizeof(y));
        cin >> n >> m;

        for (int i = 1; i <= n; i++)
            cin >> x[i] >> y[i];

        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (x[i] != x[j] && (y[i]*x[j] - x[i]*y[j]) / (x[i] - x[j]) < 0) {
                    a[i][j] = a[j][i] = (y[i] * x[j] - x[i] * y[j]) / (x[i] - x[j]) / x[i] / x[j];
                    b[i][j] = b[j][i] = (y[i] * x[j] * x[j] - y[j] * x[i] * x[i]) / (x[i] - x[j]) / x[i] / x[j];
                }

                //cout<<i<<' '<<j<<' '<<a[i][j]<<' '<<a[j][i]<<' '<<b[i][j]<<' '<<b[j][i]<<endl;
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                if (a[i][j] < 0)
                    re[i]++;

            //cout<<re[i]<<" ";
        }

        //cout<<endl;
        while (cnt1 != n) {
            cnt = 0;

            if (cnt1 == n - 1) {
                ans++;
                break;
            }

            for (int i = 1; i <= n; i++)
                if (!f[i]) {
                    num = 1;

                    for (int j = 1; j <= n; j++)
                        if (!f[j] && a[i][j] < 0) {
                            num = 2;

                            for (int k = 1; k <= n; k++) {
                                if (!f[k] && k != j && fabs(a[i][j] - a[i][k]) <= 1e-10 && fabs(b[i][j] - b[i][k]) <= 1e-10) {
                                    num++;
                                }
                            }

                            if (num > cnt || (num == cnt && (re[i] < re[id] || (re[i] == re[id] && re[j] < re[id1])))) {
                                cnt = num;
                                id = i;
                                id1 = j;
                                ida = a[i][j];
                                idb = b[i][j];
                            }

                            //cout<<i<<' '<<j<<' '<<num<<endl;
                        }

                    if (num == 1 && (num > cnt || (num == cnt && re[i] < re[id]))) {
                        cnt = num;
                        id = i;
                    }

                }

            //cout<<id<<' ';
            if (cnt > 1) {
                f[id] = true;

                for (int i = 1; i <= n; i++) {
                    if (fabs(ida - a[i][id]) <= 1e-10 && fabs(idb - b[i][id]) <= 1e-10) {
                        f[i] = true; //cout<<i<<' ';

                        for (int j = 1; j <= n; j++) {
                            if (a[i][j] < 0)
                                re[j]--;
                        }

                    }
                }

                for (int j = 1; j <= n; j++) {
                    if (a[id][j] < 0)
                        re[j]--;
                }

                //cout<<endl;
                /*for(int i=1; i<=n; i++)
                    if(!f[i]) cout<<re[i]<<" ";
                    else cout<<0<<' ';*/
            } else
                f[id] = true;

            //cout<<endl;
            cnt1 += cnt;
            ans++;
        }

        cout << ans << endl;
    }

    return 0;
}
/*
1
18 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
*/
源文件, 语言: C++23

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 3ms
memory: 3284kb

input:

10
1 0
0.79 1.72
1 0
4.38 5.62
2 0
2.27 0.62
6.40 7.87
1 0
9.86 4.10
1 0
2.28 6.10
2 0
1.16 6.35
1.6...

output:

1
1
2
1
1
1
1
2
1
2

result:

ok 10 tokens

Test #2:

score: 5
Accepted
time: 2ms
memory: 3284kb

input:

30
1 0
4.14 4.17
2 0
9.65 9.04
0.77 8.88
2 0
9.83 0.49
8.82 8.94
2 0
3.54 5.72
2.90 5.03
1 0
0.32 7....

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 30 tokens

Test #3:

score: 5
Accepted
time: 3ms
memory: 3336kb

input:

10
3 0
6.29 4.49
7.23 7.86
4.21 1.55
2 0
8.33 1.96
6.75 6.34
3 0
9.84 8.29
9.98 9.82
4.80 0.43
3 0
7...

output:

3
1
3
2
1
1
2
1
1
2

result:

ok 10 tokens

Test #4:

score: 5
Accepted
time: 1ms
memory: 3544kb

input:

30
2 0
1.29 6.49
0.24 4.53
1 0
8.43 9.43
1 0
8.91 2.38
3 0
8.20 4.50
6.53 4.49
4.65 3.79
1 0
7.33 1....

output:

1
1
1
2
1
3
3
2
2
1
1
1
2
2
1
1
3
2
2
1
1
1
2
2
3
3
1
3
1
3

result:

ok 30 tokens

Test #5:

score: 5
Accepted
time: 3ms
memory: 3480kb

input:

10
2 0
5.41 2.39
0.81 5.42
1 0
7.05 8.02
2 0
7.37 6.21
5.93 7.65
4 0
2.50 2.14
6.99 6.68
2.15 7.41
8...

output:

1
1
1
3
4
2
2
1
2
2

result:

ok 10 tokens

Test #6:

score: 5
Accepted
time: 2ms
memory: 3600kb

input:

30
4 0
4.80 8.77
0.43 4.19
1.77 6.13
8.13 3.46
1 0
4.54 8.32
4 0
6.34 4.80
1.50 0.38
6.41 5.13
6.32 ...

output:

2
1
4
2
2
4
2
2
1
2
1
4
4
1
2
2
2
2
2
1
3
2
1
1
4
1
2
1
2
1

result:

ok 30 tokens

Test #7:

score: 5
Accepted
time: 3ms
memory: 3548kb

input:

10
3 0
5.16 3.47
0.40 8.82
6.83 6.06
4 0
3.12 4.48
6.93 2.77
2.76 0.35
7.43 6.90
4 0
0.43 7.78
6.44 ...

output:

2
3
2
3
2
3
4
3
2
4

result:

ok 10 tokens

Test #8:

score: 5
Accepted
time: 3ms
memory: 3604kb

input:

10
5 0
5.11 6.03
6.52 0.65
6.61 3.88
7.01 4.67
7.14 9.29
6 0
4.12 0.32
4.42 3.43
9.18 9.94
6.02 6.45...

output:

4
6
3
3
3
4
3
4
3
4

result:

ok 10 tokens

Test #9:

score: 5
Accepted
time: 1ms
memory: 3596kb

input:

10
6 0
4.21 2.69
7.62 5.56
8.84 6.70
3.98 2.59
3.64 0.24
8.57 4.01
6 0
5.03 8.28
8.12 1.22
3.13 0.99...

output:

4
3
4
3
5
4
6
4
4
4

result:

ok 10 tokens

Test #10:

score: 5
Accepted
time: 0ms
memory: 3548kb

input:

10
7 0
5.12 1.23
2.34 4.41
4.30 0.91
4.36 0.65
5.88 2.15
8.13 6.07
2.28 5.92
8 0
5.86 5.06
5.86 4.85...

output:

4
5
4
5
6
4
4
5
4
4

result:

ok 10 tokens

Test #11:

score: 5
Accepted
time: 0ms
memory: 3548kb

input:

30
9 0
0.75 1.72
3.16 5.42
6.91 2.58
7.48 0.50
6.22 5.04
8.20 7.85
7.01 1.96
1.94 5.41
5.14 2.28
9 0...

output:

5
5
4
4
4
5
4
4
5
4
7
6
4
5
4
4
6
8
4
5
5
5
4
4
5
5
5
5
4
5

result:

ok 30 tokens

Test #12:

score: 5
Accepted
time: 4ms
memory: 3548kb

input:

30
9 0
6.04 5.24
6.47 8.32
1.99 1.85
6.19 8.10
2.76 1.05
3.22 4.96
5.78 3.89
3.17 1.14
5.14 0.24
9 0...

output:

5
5
5
5
5
5
6
5
5
5
5
6
5
6
5
5
5
5
5
5
5
6
5
5
5
5
5
5
5
5

result:

ok 30 tokens

Test #13:

score: 5
Accepted
time: 5ms
memory: 3548kb

input:

30
12 1
8.27 2.37
2.40 7.46
5.00 9.30
0.50 2.01
1.00 3.78
2.00 6.60
6.50 7.41
8.00 3.36
6.00 8.28
4....

output:

2
5
4
4
5
2
5
5
4
5
5
5
5
5
5
4
5
5
5
4
4
5
4
3
5
5
5
5
5
5

result:

ok 30 tokens

Test #14:

score: 5
Accepted
time: 0ms
memory: 3604kb

input:

30
12 2
4.00 8.00
5.44 6.58
3.65 1.77
6.01 9.81
4.17 3.10
3.24 1.34
9.80 2.17
4.66 0.85
1.00 5.00
5....

output:

6
6
5
6
5
6
6
5
6
5
6
6
5
6
6
5
6
6
6
5
6
5
5
6
6
6
6
5
6
6

result:

ok 30 tokens

Test #15:

score: 5
Accepted
time: 2ms
memory: 3596kb

input:

15
13 0
0.22 5.64
6.67 5.12
3.80 5.62
2.68 0.32
5.94 8.56
1.33 0.43
9.94 1.97
4.02 2.31
7.01 2.61
7....

output:

7
7
7
7
7
8
7
7
7
7
7
7
7
8
7

result:

ok 15 tokens

Test #16:

score: 5
Accepted
time: 3ms
memory: 3288kb

input:

15
14 1
6.86 0.90
4.65 5.15
1.50 3.74
6.50 1.88
4.50 5.28
0.50 1.47
1.00 2.72
4.00 5.57
5.00 4.76
6....

output:

6
5
5
6
6
5
5
5
6
6
5
5
5
6
6

result:

ok 15 tokens

Test #17:

score: 5
Accepted
time: 5ms
memory: 3320kb

input:

15
15 2
8.27 8.60
2.00 4.00
5.46 1.68
3.00 3.00
5.77 7.87
5.32 5.60
1.50 3.75
1.00 3.00
5.37 7.33
7....

output:

7
6
7
6
6
7
7
6
6
6
6
7
7
7
7

result:

ok 15 tokens

Test #18:

score: 5
Accepted
time: 1ms
memory: 3548kb

input:

5
18 0
9.13 3.37
2.75 6.84
5.49 4.05
5.65 2.79
6.06 3.34
3.01 2.34
8.19 4.74
9.61 8.58
4.11 6.15
5.8...

output:

10
9
10
9
10

result:

ok 5 tokens

Test #19:

score: 5
Accepted
time: 0ms
memory: 3612kb

input:

5
18 1
4.33 4.63
4.50 6.75
6.67 8.72
1.50 3.75
2.00 4.00
2.19 2.59
6.83 8.11
3.50 1.75
2.50 3.75
2.0...

output:

6
6
5
5
6

result:

ok 5 tokens

Test #20:

score: 5
Accepted
time: 0ms
memory: 3544kb

input:

5
18 2
4.50 5.03
9.10 9.36
6.22 2.15
2.59 3.72
2.15 0.76
9.53 8.02
3.88 4.51
1.50 5.25
1.00 4.00
3.6...

output:

8
7
8
7
8

result:

ok 5 tokens
中文 English

鲁ICP备2025150228号

服务器时间: 2025-04-30 07:13:50 | 开源项目