QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#678233 | #5426. Drain the Water Tank | yimg | WA | 0ms | 3736kb | C++20 | 1.2kb | 2024-10-26 14:22:59 | 2024-10-26 14:23:00 |
Judging History
answer
#include<bits/stdc++.h>
#define nxt(x) (x + 1) % n
#define lst(x) (x - 1 + n) % n
using namespace std;
void work()
{
int n;
cin >> n;
deque<pair<int, int>> a;
for(int i = 0; i < n; ++i){
int x, y; cin >> x >> y;
a.push_back({x, y});
}
while(a[0].second <= a[1].second){
a.push_back(a.front());
a.pop_front();
}
int l = 0, r = 0, ans = 0;
auto dec = [&](int c1, int c2, int c3){
int x1 = a[c1].first, x2 = a[c2].first, x3 = a[c3].first;
int y1 = a[c1].second, y2 = a[c2].second, y3 = a[c3].second;
// cout << (x1 - x2)*(y3 - y2) - (x3 - x2)*(y1 - y2) << "\n";
return (x1 - x2)*(y3 - y2) <= (x3 - x2)*(y1 - y2);
};
for(int i = 0; i < n; ++i)
{
if(a[nxt(i)].second != a[i].second){
r = i;
if(a[lst(l)].second > a[l].second && a[nxt(r)].second > a[r].second && dec(lst(l), r, nxt(r))){
ans++;
}
// cout << " HH : " << l << " " << r << " " << (a[lst(l)].second > a[l].second && a[nxt(r)].second > a[r].second) << "\n";
l = nxt(i);
}
}
cout << ans << "\n";
}
/*
7
0 5
0 3
1 3
1 2
2 2
2 1
3 1
*/
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
work();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
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: 3508kb
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: 3736kb
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: -100
Wrong Answer
time: 0ms
memory: 3592kb
input:
6 0 0 2 0 1 1 4 1 5 0 3 4
output:
1
result:
wrong answer 1st numbers differ - expected: '2', found: '1'