QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#662001#5426. Drain the Water TankSunwkingWA 0ms3636kbC++201.2kb2024-10-20 19:57:502024-10-20 19:58:35

Judging History

你现在查看的是最新测评结果

  • [2024-10-20 19:58:35]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3636kb
  • [2024-10-20 19:57:50]
  • 提交

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'