QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#740222 | #5426. Drain the Water Tank | Zawos# | WA | 0ms | 3784kb | C++14 | 1.3kb | 2024-11-13 04:21:42 | 2024-11-13 04:21:43 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vi=vector<int>;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//上
struct pt{
ll x,y;
pt():x(0),y(0){}
pt(ll x,ll y): x(x),y(y){}
pt operator+(pt p){return pt(x+p.x,y+p.y);}
pt operator-(pt p){return pt(x-p.x,y-p.y);}
ll cross(pt p){return (*this).x*p.y-(*this).y*p.x;}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin >> n;
vector<pt> v(n);
FOR(i,0,n) cin >> v[i].x >> v[i].y;
int index = 0;
for(int i = 0; i< n; i++){
if(v[(i+1)%n].y > v[i].y){
index = i;
break;
}
}
int p1 = (index+1)%n;
int ans = 0;
int need = 0;
for(int i = 0; i < n; i++){
if(v[(p1+1)%n].y < v[p1].y){
need = 1;
}
if(need && v[(p1+1)%n].y > v[p1].y && (v[(p1+1)%n]-v[p1]).cross(v[(p1+n-1)%n]-v[(p1)%n]) >= 0){
ans++;
need = 0;
}
p1++;
p1%=n;
}
cout << ans <<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3524kb
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: 3544kb
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: 3548kb
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: 3752kb
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: 3520kb
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: 3544kb
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: 3480kb
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: 3724kb
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: 3448kb
input:
3 0 0 100 0 0 100
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
3 200 0 100 100 0 0
output:
1
result:
ok 1 number(s): "1"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
3 50 50 100 50 100 100
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
3 3 0 0 4 0 0
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
3 10000 10000 -10000 10000 10000 9999
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
3 10000 10000 -10000 10000 10000 9900
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
3 10000 10000 9999 10000 10000 -10000
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
3 0 0 200 0 100 173
output:
1
result:
ok 1 number(s): "1"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
3 0 0 200 0 100 1
output:
1
result:
ok 1 number(s): "1"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
3 -10000 -10000 10000 9999 9999 10000
output:
1
result:
ok 1 number(s): "1"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3456kb
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: 3596kb
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: 3524kb
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: 3724kb
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: 3524kb
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: 3592kb
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: 3524kb
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: 3444kb
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: 3520kb
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: 3520kb
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: 3596kb
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: 3448kb
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: 3448kb
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: 3524kb
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: 3720kb
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: 3716kb
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: 3568kb
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: 3520kb
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: 3452kb
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: 3464kb
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: 3748kb
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: 3448kb
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: 3544kb
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: 3720kb
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: 3784kb
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: 3724kb
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: 3784kb
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: 3448kb
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: 3572kb
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: 3516kb
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: 3596kb
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: 3744kb
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: 3672kb
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: 3516kb
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: 3452kb
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: 3520kb
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: 3784kb
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: -100
Wrong Answer
time: 0ms
memory: 3748kb
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:
3
result:
wrong answer 1st numbers differ - expected: '1', found: '3'