QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786850 | #5426. Drain the Water Tank | Awei | WA | 0ms | 3636kb | C++14 | 2.3kb | 2024-11-27 00:07:52 | 2024-11-27 00:07:54 |
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 = 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 << 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: 0
Wrong Answer
time: 0ms
memory: 3636kb
input:
6 0 0 1 1 2 1 3 0 3 2 0 2
output:
1
result:
wrong answer 1st numbers differ - expected: '2', found: '1'