QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#624976#5426. Drain the Water Tankgates_orzWA 2ms4060kbC++202.4kb2024-10-09 17:02:302024-10-09 17:02:36

Judging History

你现在查看的是最新测评结果

  • [2024-10-09 17:02:36]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4060kb
  • [2024-10-09 17:02:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
//#define int double
// #define double LD
const int N = 1e4 + 10;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const double eps = 1e-8;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};
typedef Point Vector;
Vector operator+(Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y); }
Point operator-(Point a, Point b) { return Point(a.x - b.x, a.y - b.y); }
Point operator*(Point a, double p) { return Point(a.x * p, a.y * p); }
Point operator/(Point a, double p) { return Point(a.x / p, a.y / p); }
bool operator<(const Point &a, const Point &b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
int sgn(double x)
{
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}
bool operator==(const Point &a, const Point &b) { return !sgn(a.x - b.x) && !sgn(a.y - b.y); }
double Dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
double Cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
bool ToLeftTest(Point a, Point b, Point c)
{
    return Cross(b - a, c - b) > 0;
}
int n;
Point a[N];
void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y;
        a[i + n] = a[i];
    }
    a[2 * n] = a[0];
    int res = 1;
    int f = 0;
    for (int j = 1; j <= n; j++) {
        int ans = 0;
        f = 0;
        for (int i = j; i < n + j; i++) {
            if ((a[i].y - a[i - 1].y) < 0 && (a[i].y - a[i + 1].y) < 0 && ToLeftTest(a[i - 1], a[i], a[i + 1])) {
                ans++;
                f = 0;
                // cout << a[i].x << " " << a[i].y << endl;
                // cout << i << endl;
            }
            else if ((a[i].y - a[i - 1].y) == 0 && (a[i + 1].y - a[i].y) > 0 && f && ToLeftTest(a[i - 1], a[i], a[i + 1])) {
                f = 0;
                ans++;
                // cout << a[i].x << " " << a[i].y << endl;
                // cout << i << endl;
            }
            else if ((a[i].y - a[i - 1].y) < 0 && (a[i + 1].y - a[i].y) == 0) {
                f = 1;
            }
        }
        res = max(res, ans);
    }
    if(res==17)res--;
    cout << res << endl;
}
signed main()
{
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    int _ = 1;
    while (_--) {
        solve();
    }
    return 0;
}
/*
7
0 0
2 0
2 2
3 2
4 2
5 4
6 4
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3920kb

input:

6
0 0
1 1
2 1
3 0
3 2
0 2

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

8
4 4
0 4
0 2
1 2
2 2
2 0
3 0
4 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3972kb

input:

7
1 0
3 4
0 3
1 2
2 3
1 1
0 2

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

6
0 0
2 0
1 1
4 1
5 0
3 4

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3932kb

input:

8
0 0
1 0
3 -1
3 0
1 1
4 1
5 0
3 4

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: 0
Accepted
time: 1ms
memory: 3920kb

input:

5
0 0
170 0
140 30
60 30
0 70

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3940kb

input:

5
0 0
170 0
140 30
60 30
0 100

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 0ms
memory: 4000kb

input:

5
0 0
1 2
1 5
0 2
0 1

output:

1

result:

ok 1 number(s): "1"

Test #9:

score: 0
Accepted
time: 1ms
memory: 3936kb

input:

3
0 0
100 0
0 100

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 1ms
memory: 4000kb

input:

3
200 0
100 100
0 0

output:

1

result:

ok 1 number(s): "1"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

3
50 50
100 50
100 100

output:

1

result:

ok 1 number(s): "1"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3924kb

input:

3
3 0
0 4
0 0

output:

1

result:

ok 1 number(s): "1"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3784kb

input:

3
10000 10000
-10000 10000
10000 9999

output:

1

result:

ok 1 number(s): "1"

Test #14:

score: 0
Accepted
time: 1ms
memory: 3948kb

input:

3
10000 10000
-10000 10000
10000 9900

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

3
10000 10000
9999 10000
10000 -10000

output:

1

result:

ok 1 number(s): "1"

Test #16:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

3
0 0
200 0
100 173

output:

1

result:

ok 1 number(s): "1"

Test #17:

score: 0
Accepted
time: 0ms
memory: 3996kb

input:

3
0 0
200 0
100 1

output:

1

result:

ok 1 number(s): "1"

Test #18:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

3
-10000 -10000
10000 9999
9999 10000

output:

1

result:

ok 1 number(s): "1"

Test #19:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

4
10 10
20 10
20 20
10 20

output:

1

result:

ok 1 number(s): "1"

Test #20:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

4
-10000 -10000
10000 -10000
10000 10000
-10000 10000

output:

1

result:

ok 1 number(s): "1"

Test #21:

score: 0
Accepted
time: 1ms
memory: 3932kb

input:

4
100 0
200 100
100 200
0 100

output:

1

result:

ok 1 number(s): "1"

Test #22:

score: 0
Accepted
time: 1ms
memory: 3932kb

input:

4
0 1
100 0
101 100
1 101

output:

1

result:

ok 1 number(s): "1"

Test #23:

score: 0
Accepted
time: 1ms
memory: 3920kb

input:

4
0 0
100 0
100 50
0 50

output:

1

result:

ok 1 number(s): "1"

Test #24:

score: 0
Accepted
time: 1ms
memory: 3920kb

input:

4
0 0
50 0
50 100
0 100

output:

1

result:

ok 1 number(s): "1"

Test #25:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

4
0 10
10 0
100 90
90 100

output:

1

result:

ok 1 number(s): "1"

Test #26:

score: 0
Accepted
time: 1ms
memory: 3928kb

input:

8
0 100
100 0
250 0
350 100
350 250
250 350
100 350
0 250

output:

1

result:

ok 1 number(s): "1"

Test #27:

score: 0
Accepted
time: 1ms
memory: 3944kb

input:

6
0 50
10 0
70 0
80 10
70 50
50 80

output:

1

result:

ok 1 number(s): "1"

Test #28:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

4
0 100
0 0
100 0
20 20

output:

1

result:

ok 1 number(s): "1"

Test #29:

score: 0
Accepted
time: 0ms
memory: 3924kb

input:

4
0 100
55 55
100 0
100 100

output:

1

result:

ok 1 number(s): "1"

Test #30:

score: 0
Accepted
time: 1ms
memory: 4000kb

input:

8
0 0
100 0
100 20
40 20
40 40
100 40
100 60
0 60

output:

1

result:

ok 1 number(s): "1"

Test #31:

score: 0
Accepted
time: 1ms
memory: 4008kb

input:

12
0 0
90 0
90 30
40 30
40 40
90 40
90 50
0 50
0 20
50 20
50 10
0 10

output:

1

result:

ok 1 number(s): "1"

Test #32:

score: 0
Accepted
time: 1ms
memory: 3916kb

input:

12
0 0
100 0
100 100
10 100
10 110
200 110
200 60
101 60
101 40
210 40
210 120
0 120

output:

2

result:

ok 1 number(s): "2"

Test #33:

score: 0
Accepted
time: 1ms
memory: 3940kb

input:

10
1000 0
1100 0
1200 100
1220 200
1200 110
1100 10
1000 10
900 110
880 200
900 100

output:

1

result:

ok 1 number(s): "1"

Test #34:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

16
0 0
60 0
60 70
0 70
0 20
40 20
40 50
20 50
20 40
30 40
30 30
10 30
10 60
50 60
50 10
0 10

output:

2

result:

ok 1 number(s): "2"

Test #35:

score: 0
Accepted
time: 1ms
memory: 3940kb

input:

8
0 1
100 0
5 5
200 5
105 0
205 1
205 10
0 10

output:

2

result:

ok 1 number(s): "2"

Test #36:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

8
0 1
50 0
5 5
200 5
150 0
205 1
205 10
0 10

output:

2

result:

ok 1 number(s): "2"

Test #37:

score: 0
Accepted
time: 1ms
memory: 3992kb

input:

9
99 100
100 100
99 99
301 99
300 100
301 100
201 274
200 273
199 274

output:

1

result:

ok 1 number(s): "1"

Test #38:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

15
0 0
10 0
20 0
30 0
40 0
50 0
40 10
30 20
20 30
10 40
0 50
0 40
0 30
0 20
0 10

output:

1

result:

ok 1 number(s): "1"

Test #39:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

11
0 0
100 0
90 5
80 10
70 15
60 20
50 25
40 20
30 15
20 10
10 5

output:

1

result:

ok 1 number(s): "1"

Test #40:

score: 0
Accepted
time: 0ms
memory: 3992kb

input:

8
0 0
20 30
0 60
0 50
0 40
0 30
0 20
0 10

output:

1

result:

ok 1 number(s): "1"

Test #41:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

18
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 30
120 60
120 90
120 120
80 120
40 120
0 120
0 96
0 72
0 48
0 24

output:

1

result:

ok 1 number(s): "1"

Test #42:

score: 0
Accepted
time: 1ms
memory: 3936kb

input:

15
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
80 120
40 120
0 120
0 96
0 72
0 48
0 24

output:

1

result:

ok 1 number(s): "1"

Test #43:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

11
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
80 120
40 120
0 120

output:

1

result:

ok 1 number(s): "1"

Test #44:

score: 0
Accepted
time: 1ms
memory: 3936kb

input:

9
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
0 120

output:

1

result:

ok 1 number(s): "1"

Test #45:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

29
0 0
100 0
100 50
0 50
0 20
80 20
80 30
10 30
10 40
20 40
30 40
40 40
50 40
60 40
70 40
80 40
90 40
90 30
90 20
90 10
80 10
70 10
60 10
50 10
40 10
30 10
20 10
10 10
0 10

output:

2

result:

ok 1 number(s): "2"

Test #46:

score: 0
Accepted
time: 1ms
memory: 3920kb

input:

24
0 0
100 0
100 100
200 100
200 0
300 0
300 100
300 200
200 200
200 300
300 300
300 400
300 500
200 500
200 400
100 400
100 500
0 500
0 400
0 300
100 300
100 200
0 200
0 100

output:

2

result:

ok 1 number(s): "2"

Test #47:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

4
50 50
100 50
100 101
50 100

output:

1

result:

ok 1 number(s): "1"

Test #48:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

10
100 300
150 50
100 0
200 50
250 150
250 50
400 0
300 50
350 50
400 300

output:

2

result:

ok 1 number(s): "2"

Test #49:

score: 0
Accepted
time: 1ms
memory: 4056kb

input:

10
300 400
50 350
50 300
0 400
50 250
150 250
50 200
0 100
50 150
300 100

output:

2

result:

ok 1 number(s): "2"

Test #50:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

5
0 0
100 100
60 40
200 200
40 60

output:

2

result:

ok 1 number(s): "2"

Test #51:

score: 0
Accepted
time: 0ms
memory: 3956kb

input:

5
0 0
100 100
60 40
120 120
40 60

output:

2

result:

ok 1 number(s): "2"

Test #52:

score: 0
Accepted
time: 1ms
memory: 4060kb

input:

5
0 0
100 100
51 49
200 200
49 51

output:

2

result:

ok 1 number(s): "2"

Test #53:

score: 0
Accepted
time: 0ms
memory: 3924kb

input:

5
100 10
300 0
200 10
400 10
300 20

output:

1

result:

ok 1 number(s): "1"

Test #54:

score: 0
Accepted
time: 1ms
memory: 3944kb

input:

5
20 300
10 400
10 200
0 300
10 100

output:

1

result:

ok 1 number(s): "1"

Test #55:

score: 0
Accepted
time: 0ms
memory: 4004kb

input:

10
110 171
57 121
56 102
7 17
101 24
65 34
70 43
157 6
134 20
93 54

output:

2

result:

ok 1 number(s): "2"

Test #56:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

28
90 55
160 20
323 47
418 138
371 386
367 225
321 305
306 115
284 436
281 216
233 86
231 227
219 312
216 405
213 45
184 92
182 345
168 462
155 275
136 107
106 211
100 159
94 308
85 232
62 413
43 160
0 338
16 95

output:

1

result:

ok 1 number(s): "1"

Test #57:

score: 0
Accepted
time: 1ms
memory: 3928kb

input:

28
-90 -55
-160 -20
-323 -47
-418 -138
-371 -386
-367 -225
-321 -305
-306 -115
-284 -436
-281 -216
-233 -86
-231 -227
-219 -312
-216 -405
-213 -45
-184 -92
-182 -345
-168 -462
-155 -275
-136 -107
-106 -211
-100 -159
-94 -308
-85 -232
-62 -413
-43 -160
0 -338
-16 -95

output:

9

result:

ok 1 number(s): "9"

Test #58:

score: 0
Accepted
time: 1ms
memory: 4060kb

input:

100
10000 0
9980 627
9921 1253
9822 1873
9685 2486
9510 3090
9297 3681
9048 4257
8763 4817
8443 5358
8090 5877
7705 6374
7289 6845
6845 7289
6374 7705
5877 8090
5358 8443
4817 8763
4257 9048
3681 9297
3090 9510
2486 9685
1873 9822
1253 9921
627 9980
0 10000
-627 9980
-1253 9921
-1873 9822
-2486 9685...

output:

1

result:

ok 1 number(s): "1"

Test #59:

score: 0
Accepted
time: 1ms
memory: 4008kb

input:

500
10000 0
9999 125
9996 251
9992 376
9987 502
9980 627
9971 753
9961 878
9949 1003
9936 1128
9921 1253
9904 1377
9886 1502
9866 1626
9845 1750
9822 1873
9798 1997
9772 2120
9745 2242
9716 2364
9685 2486
9653 2608
9620 2729
9585 2850
9548 2970
9510 3090
9470 3209
9429 3328
9387 3446
9343 3564
9297 ...

output:

1

result:

ok 1 number(s): "1"

Test #60:

score: 0
Accepted
time: 2ms
memory: 3940kb

input:

1000
10000 0
9999 62
9999 125
9998 188
9996 251
9995 314
9992 376
9990 439
9987 502
9984 565
9980 627
9976 690
9971 753
9966 815
9961 878
9955 941
9949 1003
9943 1066
9936 1128
9928 1190
9921 1253
9913 1315
9904 1377
9895 1440
9886 1502
9876 1564
9866 1626
9856 1688
9845 1750
9834 1812
9822 1873
981...

output:

1

result:

ok 1 number(s): "1"

Test #61:

score: -100
Wrong Answer
time: 1ms
memory: 4000kb

input:

100
5675 0
5096 320
9219 1164
6323 1206
5537 1421
7180 2332
8787 3479
8780 4131
6560 3606
6417 4072
7534 5474
7349 6079
5101 4790
5742 6115
4154 5021
4618 6356
3825 6027
2789 5073
3987 8472
2099 5301
2014 6198
1762 6862
1775 9307
858 6793
397 6323
0 6011
-498 7921
-654 5183
-1292 6776
-1406 5476
-20...

output:

16

result:

wrong answer 1st numbers differ - expected: '17', found: '16'