QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #693459 | #5426. Drain the Water Tank | Yuanyin26 | WA | 1ms | 3860kb | C++20 | 1.8kb | 2024-10-31 16:12:05 | 2024-10-31 16:12:08 |
Judging History
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)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();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
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: 3624kb
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: 3852kb
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: 3580kb
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: 3496kb
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: 3836kb
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: 3852kb
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: 3608kb
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: 3608kb
input:
3 0 0 100 0 0 100
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
3 200 0 100 100 0 0
output:
1
result:
ok 1 number(s): "1"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3 50 50 100 50 100 100
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
3 3 0 0 4 0 0
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
3 10000 10000 -10000 10000 10000 9999
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
3 10000 10000 -10000 10000 10000 9900
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
3 10000 10000 9999 10000 10000 -10000
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
3 0 0 200 0 100 173
output:
1
result:
ok 1 number(s): "1"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
3 0 0 200 0 100 1
output:
1
result:
ok 1 number(s): "1"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
3 -10000 -10000 10000 9999 9999 10000
output:
1
result:
ok 1 number(s): "1"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3808kb
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: 3852kb
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: 3556kb
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: 3608kb
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: 3552kb
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: 3552kb
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: 3776kb
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: 3552kb
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: 3552kb
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: 3612kb
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: 3612kb
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: 3624kb
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: 3620kb
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: 3612kb
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: 3860kb
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: 3548kb
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: 3608kb
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: 3848kb
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: 3840kb
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: 3552kb
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: 3776kb
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: 3604kb
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: 3840kb
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: 3616kb
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: 3620kb
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: 3492kb
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: 3500kb
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: 3552kb
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: 3612kb
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: 3496kb
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: 3604kb
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: 3848kb
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: 3612kb
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: 1ms
memory: 3544kb
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: 3616kb
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: 3644kb
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: 3804kb
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: 3496kb
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: 3564kb
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: 3672kb
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: 0ms
memory: 3500kb
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:
20
result:
wrong answer 1st numbers differ - expected: '17', found: '20'