QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786857 | #5426. Drain the Water Tank | Awei | WA | 0ms | 3836kb | C++14 | 2.3kb | 2024-11-27 00:09:35 | 2024-11-27 00:09:36 |
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 ok1 = false, ok2 = true;
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 << ok2 << endl;
if(b[i].y > 0){
if(ok2 && (down.x != 0 || down.y != 0)){
if(ok1) ans++;
else if(cross(down, b[i]) >= 0){
ans++;
}
}
ok1 = false;
down = {0, 0};
}else if(b[i].y < 0){
down = b[i];
}else if(b[i].x > 0){
ok1 = true;
}
if(b[i].x < 0) ok2 = false;
else if(b[i].x > 0) ok2 = true;
// cout << ok2 << 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: 3636kb
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: 3836kb
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: 3828kb
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: 3540kb
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: 3540kb
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: 3536kb
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: 3540kb
input:
5 0 0 170 0 140 30 60 30 0 100
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3832kb
input:
5 0 0 1 2 1 5 0 2 0 1
output:
0
result:
wrong answer 1st numbers differ - expected: '1', found: '0'