QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786831 | #5426. Drain the Water Tank | Awei | WA | 0ms | 3828kb | C++14 | 2.3kb | 2024-11-26 23:53:27 | 2024-11-26 23:53:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
struct point{
double x, y;
};
double cross(point a, point b){
// cout << a.x * b.y - b.x * a.y << endl;
return a.x * b.y - b.x * a.y;
}
void solve(){
int n;
cin >> n;
int lid = 1;
vector<pair<int, int>> a(2 * n + 1);
for(int i = 1; i <= n; i++){
cin >> a[i].first >> a[i].second;
if(a[i].second > a[lid].second) lid = i;
else if(a[i].second == a[lid].second && a[i].first < a[lid].first) lid = i;
}
for(int i = 1; i <= n; i++){
a[n + i] = a[i];
}
vector<point> b;
int lx = a[lid].first;
int ly = a[lid].second;
for(int i = lid + 1; i <= n + lid; i++){
int x = a[i].first;
int y = a[i].second;
b.push_back({x - lx, y - ly});
lx = x; ly = y;
}
int ans = 0;
bool ok = false;
point down = {0, 0};
for(int i = 0; i < b.size(); i++){
// cout << i << endl;
// cout << down.x << " " << down.y << endl;
// cout << b[i].x << " " << b[i].y << endl;
// cout << ok << endl;
if(b[i].y > 0){
if(down.x != 0 || down.y != 0){
if(ok) ans++;
else if(cross(down, b[i]) >= 0){
ans++;
}
}
ok = false;
down = {0, 0};
}else if(b[i].y < 0){
down = b[i];
}else if(b[i].x > 0){
ok = true;
}
// cout << ok << endl;
// cout << ans << endl;
// cout << "-------" << endl;
}
// auto [lx, ly] = a[lid];
// for(int i = lid + 1; i <= n + lid; i++){
// auto [x, y] = a[i];
// auto [xx, yy] = a[i + 1];
// // cout << i << endl;
// // cout << lx << " " << ly << endl;
// // cout << x << " " << y << endl;
// // cout << xx << " " << yy << endl;
// if(y > ly){
// lx = x;
// ly = y;
// }
// if(yy > y && cross(x - lx, y - ly, xx - x, yy - y) >= 0){
// lx = xx;
// ly = yy;
// ans++;
// }
// // cout << ans << endl;
// // cout << "-------" << endl;
// }
cout << ans << "\n";
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while(T--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
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: 3608kb
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: 3508kb
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: 3548kb
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: 3588kb
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: 3592kb
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: 3524kb
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: 3604kb
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: 3524kb
input:
3 0 0 100 0 0 100
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
3 200 0 100 100 0 0
output:
1
result:
ok 1 number(s): "1"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
3 50 50 100 50 100 100
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
3 3 0 0 4 0 0
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
3 10000 10000 -10000 10000 10000 9999
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
3 10000 10000 -10000 10000 10000 9900
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
3 10000 10000 9999 10000 10000 -10000
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
3 0 0 200 0 100 173
output:
1
result:
ok 1 number(s): "1"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3528kb
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: 3620kb
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: 3524kb
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: 3532kb
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: 3784kb
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: 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: 3532kb
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: 3588kb
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: 3608kb
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: 3744kb
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: 3540kb
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: 3808kb
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: 3608kb
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: 3812kb
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: 3576kb
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: -100
Wrong Answer
time: 0ms
memory: 3612kb
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:
3
result:
wrong answer 1st numbers differ - expected: '2', found: '3'