QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#693608#5426. Drain the Water TankYuanyin26WA 0ms3856kbC++202.2kb2024-10-31 16:27:412024-10-31 16:27:42

Judging History

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

  • [2024-10-31 16:27:42]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3856kb
  • [2024-10-31 16:27:41]
  • 提交

answer

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<string.h>
#include <string>
#include<math.h>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<map>
#include<queue>
#include<stack>
#include<functional>
#include<deque>
using namespace std;

#define MAXN 301000;
#define ll long long
#define lll unsigned long long
#define PA pair<ll,ll>
#define INF (ll)0x3f3f3f3f*(ll)1000000
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const ll mod = 1e9 + 7;

struct node {
	int x, y;
};

void solve() {
	int n; cin >> n;
	vector<node>arr(2 * n);

	bool c = false;
	for (int i = 0; i < n; i++) {
		cin >> arr[i].x >> arr[i].y;
		arr[i + n] = arr[i];

		if (arr[i + n].y != arr[i - 1 + n].y)c = true;
	}

	if (!c) {
		cout << 0 << endl;
		return;
	}

	vector<bool>visit(n, false);
	int cnt = 0;
	for (int i = n; i < 2 * n; i++) {
		if (visit[i % n])continue;

		int l = i - 1, r = (i + 1) % (2 * n);
		while (arr[l].y == arr[i].y)l--;
		while (arr[r].y == arr[i].y)r = (r + 1) % (2 * n);

		int p = r - 1;
		if (p < 0)p = 2 * n - 1;
		while (p != l) {
			visit[p % n] = true;
			p--;
			if (p < 0)p = 2 * n - 1;
		}
		if (arr[i].y < arr[l].y && arr[i].y < arr[r].y)
		{
			if (arr[l].x <= arr[r].x)
			{

				double k1;
				double k2;
				if ((arr[l].x - arr[i].x) == 0)k1 = 1;
				else k1 = (double)(arr[l].y - arr[i].y) / (arr[l].x - arr[i].x);
				if ((arr[r].x - arr[i].x) == 0)k2 = 1;
				else k2 = (double)(arr[r].y - arr[i].y) / (arr[r].x - arr[i].x);

				if (arr[l].x <= arr[i].x && arr[i].x <= arr[r].x)cnt++;
				else if (k1 >= k2)cnt++;
			}
			else
			{
				double k1;
				double k2;
				if ((arr[l].x - arr[i].x) == 0)k1 = 1;
				else k1 = (double)(arr[l].y - arr[i].y) / (arr[l].x - arr[i].x);
				if ((arr[r].x - arr[i].x) == 0)k2 = 1;
				else k2 = (double)(arr[r].y - arr[i].y) / (arr[r].x - arr[i].x);
				if (k1 > k2)
				{
					if (arr[r].x <= arr[i].x && arr[i].x <= arr[l].x);
					else cnt++;
				}
			}
		}
		

	}
	cout << cnt << endl;
}
int main() {
	IOS;
	int t = 1;// cin >> t;
	while (t--) {
		solve();
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3656kb

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: 3772kb

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: 0ms
memory: 3496kb

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: 0ms
memory: 3616kb

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: 0ms
memory: 3548kb

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: 0ms
memory: 3776kb

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: 0ms
memory: 3604kb

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: 3648kb

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: 0ms
memory: 3612kb

input:

3
0 0
100 0
0 100

output:

1

result:

ok 1 number(s): "1"

Test #10:

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

input:

3
200 0
100 100
0 0

output:

1

result:

ok 1 number(s): "1"

Test #11:

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

input:

3
50 50
100 50
100 100

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

3
3 0
0 4
0 0

output:

1

result:

ok 1 number(s): "1"

Test #13:

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

input:

3
10000 10000
-10000 10000
10000 9999

output:

1

result:

ok 1 number(s): "1"

Test #14:

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

input:

3
10000 10000
-10000 10000
10000 9900

output:

1

result:

ok 1 number(s): "1"

Test #15:

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

input:

3
10000 10000
9999 10000
10000 -10000

output:

1

result:

ok 1 number(s): "1"

Test #16:

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

input:

3
0 0
200 0
100 173

output:

1

result:

ok 1 number(s): "1"

Test #17:

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

input:

3
0 0
200 0
100 1

output:

1

result:

ok 1 number(s): "1"

Test #18:

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

input:

3
-10000 -10000
10000 9999
9999 10000

output:

1

result:

ok 1 number(s): "1"

Test #19:

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

input:

4
10 10
20 10
20 20
10 20

output:

1

result:

ok 1 number(s): "1"

Test #20:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #21:

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

input:

4
100 0
200 100
100 200
0 100

output:

1

result:

ok 1 number(s): "1"

Test #22:

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

input:

4
0 1
100 0
101 100
1 101

output:

1

result:

ok 1 number(s): "1"

Test #23:

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

input:

4
0 0
100 0
100 50
0 50

output:

1

result:

ok 1 number(s): "1"

Test #24:

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

input:

4
0 0
50 0
50 100
0 100

output:

1

result:

ok 1 number(s): "1"

Test #25:

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

input:

4
0 10
10 0
100 90
90 100

output:

1

result:

ok 1 number(s): "1"

Test #26:

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

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: 0ms
memory: 3548kb

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: 0ms
memory: 3720kb

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: 3856kb

input:

4
0 100
55 55
100 0
100 100

output:

1

result:

ok 1 number(s): "1"

Test #30:

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

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: 0ms
memory: 3496kb

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: 0ms
memory: 3556kb

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: 0ms
memory: 3544kb

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: 3544kb

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: 0ms
memory: 3544kb

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: 0ms
memory: 3616kb

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: 0ms
memory: 3652kb

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: 3604kb

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: 3612kb

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: 3584kb

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: 3840kb

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: 0ms
memory: 3500kb

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: 0ms
memory: 3620kb

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: 0ms
memory: 3616kb

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: 3544kb

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: 0ms
memory: 3548kb

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: 0ms
memory: 3772kb

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: 3512kb

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: 0ms
memory: 3648kb

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: 0ms
memory: 3552kb

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: 3604kb

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: 0ms
memory: 3648kb

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: 3548kb

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: 0ms
memory: 3476kb

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: 3608kb

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: 3584kb

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: 0ms
memory: 3608kb

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: 0ms
memory: 3492kb

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: 0ms
memory: 3624kb

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: 0ms
memory: 3668kb

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: 0
Accepted
time: 0ms
memory: 3552kb

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:

17

result:

ok 1 number(s): "17"

Test #62:

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

input:

500
9861 0
6812 85
7520 189
7380 278
5178 260
7253 456
6724 507
7648 674
6898 695
5518 626
5005 632
9331 1298
4943 751
9438 1555
6461 1148
9637 1838
5312 1082
9406 2040
8241 1896
8053 1960
8715 2237
6398 1728
5037 1429
4855 1443
7371 2293
7768 2524
8513 2884
9057 3196
6740 2474
8789 3352
5730 2269
8...

output:

82

result:

ok 1 number(s): "82"

Test #63:

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

input:

1000
8091 0
9198 57
9060 113
5747 108
5479 137
6865 215
9352 352
7129 313
5012 252
5016 283
7401 465
8909 616
9970 753
9436 772
7619 671
5368 507
6896 695
8556 917
6143 697
6802 816
9764 1233
9025 1197
8619 1199
5442 792
8519 1294
8530 1351
8292 1366
8711 1492
9103 1618
8293 1528
6769 1291
9047 1784...

output:

157

result:

ok 1 number(s): "157"

Test #64:

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

input:

100
0 0
10000 0
10000 10000
9896 9853
9793 951
9690 1642
9587 4776
9484 6666
9381 5058
9278 8146
9175 6491
9072 714
8969 1675
8865 79
8762 3597
8659 4040
8556 1707
8453 8735
8350 6676
8247 8796
8144 2579
8041 2431
7938 3240
7835 827
7731 353
7628 5638
7525 1960
7422 7770
7319 8599
7216 5076
7113 880...

output:

1

result:

ok 1 number(s): "1"

Test #65:

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

input:

500
0 0
10000 0
10000 10000
9979 4349
9959 5502
9939 255
9919 639
9899 5248
9879 974
9859 7593
9839 1091
9818 5905
9798 6216
9778 8699
9758 9951
9738 2044
9718 8181
9698 5522
9678 1888
9657 7549
9637 9475
9617 3347
9597 136
9577 775
9557 2467
9537 1000
9517 3873
9496 1460
9476 4350
9456 7880
9436 48...

output:

1

result:

ok 1 number(s): "1"

Test #66:

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

input:

1000
0 0
10000 0
10000 10000
9989 4685
9979 9134
9969 1180
9959 3397
9949 6194
9939 3697
9929 7962
9919 1358
9909 5778
9899 6522
9889 6286
9879 2382
9869 41
9859 3865
9849 997
9839 1746
9829 8380
9819 8211
9809 6070
9799 5539
9789 7476
9779 4391
9769 4092
9759 9264
9749 2333
9739 3849
9729 6011
9719...

output:

1

result:

ok 1 number(s): "1"

Test #67:

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

input:

1000
0 0
-10000 0
-10000 -10000
-9989 -4685
-9979 -9134
-9969 -1180
-9959 -3397
-9949 -6194
-9939 -3697
-9929 -7962
-9919 -1358
-9909 -5778
-9899 -6522
-9889 -6286
-9879 -2382
-9869 -41
-9859 -3865
-9849 -997
-9839 -1746
-9829 -8380
-9819 -8211
-9809 -6070
-9799 -5539
-9789 -7476
-9779 -4391
-9769 -...

output:

339

result:

ok 1 number(s): "339"

Test #68:

score: -100
Wrong Answer
time: 0ms
memory: 3616kb

input:

100
-25 0
-24 0
-23 0
-22 0
-21 0
-20 0
-19 0
-18 0
-17 0
-16 0
-15 0
-14 0
-13 0
-12 0
-11 0
-10 0
-9 0
-8 0
-7 0
-6 0
-5 0
-4 0
-3 0
-2 0
-1 0
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0
21 0
22 0
23 0
24 0
-9999 1
9999 2
-9999 3
9999 4
-9999 5
99...

output:

0

result:

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