QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#786704#5426. Drain the Water TankAweiWA 0ms3636kbC++201.4kb2024-11-26 22:58:462024-11-26 22:58:46

Judging History

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

  • [2024-11-26 22:58:46]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3636kb
  • [2024-11-26 22:58:46]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

double cross(double x1, double y1, double x2, double y2){
    // cout << x1 << " " << y1 << endl;
    // cout << x2 << " " << y2 << endl;
    return x1 * y2 - x2 * y1;
}

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];
    }

    int ans = 0;
    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: 3612kb

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: 3484kb

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: 3604kb

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'