QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662001 | #5426. Drain the Water Tank | Sunwking | WA | 0ms | 3636kb | C++20 | 1.2kb | 2024-10-20 19:57:50 | 2024-10-20 19:58:35 |
Judging History
answer
//
// Created by Lenovo on 2024/10/20.
//
#include <bits/stdc++.h>
using namespace std;
typedef int db;
struct P{
db x , y;
P(){};
P(db _x , db _y) : x(_x) , y(_y){}
P operator- (P p) {return {x - p.x , y - p.y}; }
db det(P p){return x * p.y - y * p.x;}
int quad() const {return y > 0 || y == 0 && x >= 0;}
};
int main(){
int n;
cin >> n;
vector<P> a(n);
for(int i = 0 ; i < n ; i ++ )
cin >> a[i].x >> a[i].y;
std::sort(a.begin(), a.end() , [&](auto a , auto b){
int qa = a.quad() , qb = b.quad();
if(qa != qb) return qa < qb;
return a.det(b) > 0;
});
vector<int> st(n);
int ans = 0;
for(int i = 0 ; i < n ; i ++ ){
int l = (i - 1 + n) % n;
int r = (i + 1) % n;
if(a[l].y > a[i].y && a[r].y > a[i].y && (a[i] - a[l]).det(a[r] - a[i]) > 0)
ans ++ , st[i] = 1;
}
for(int i = 0 ; i < n ; i ++ ){
int j = i + 1;
if(a[j].y != a[i].y) continue;
while(j < 2 * n && a[j % n].y <= a[(j - 1) % n].y)
j ++;
if(!st[j]){
ans ++;
st[j] = 1;
i = j + 1;
}
}
cout << ans << "\n";
}
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'