QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#760623#5426. Drain the Water Tankeinekleine18WA 0ms3568kbC++203.2kb2024-11-18 17:58:162024-11-18 17:58:16

Judging History

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

  • [2024-11-18 17:58:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3568kb
  • [2024-11-18 17:58:16]
  • 提交

answer

#include <array>
#include<bits/stdc++.h>
#include <cstddef>
#include <cstdio>
#include <iostream>
#include <vector>

#define int long long
// constexpr double eps=1e-8;
// template<typename T> struct point{
//     T x,y;
//     bool operator==(const point &a) const {
//         return std::abs(x-a.x)<=eps&&std::abs(y-a.y)<=eps;
//     }
//     T operator *(const point &a) const {
//         return x*a.x+y*a.y;
//     }
//     T operator ^(const point &a) const {
//         return x*a.y-y*a.x;
//     }
//     point operator+(const point &a) const {
//         return {x+a.y,y+a.y};
//     }
//     point operator-(const point &a) const {
//         return {x-a.y,y-a.y};
//     }
//     point operator-() const {
//         return {-x,-y};
//     }
//     int toleft(const point &a)const {
//         const auto t=(*this)^a;
//         return (t>eps)-(t<eps);
//     }
// };
// template<typename T> struct line{
//     point<T>p,v;
//     int toleft(const point<T>&a)const {
//         return v.toleft(a-p);
//     }
// };
// using Line=line<double>;
// template<typename T> struct polygon{
//     std::vector<point<T>>p;
//     size_t nxt(const size_t i) const {
//         return i==p.size()-1?0:i+1;
//     }
//     std::pair<bool,int>winding(const point<T>&a) const {
//         int cnt=0;
//         for(size_t i=0;i<p.size();++i){
//             const point<T> u=p[i],v=p[nxt(i)];
//             if(std::abs((a-u)^(a-v))<=eps&&(a-u)*(a-v)<=eps){
//                 return {true,0};
//             }
//             if(std::abs(u.y-v.y)<=eps) continue;
//             const Line uv={u,v-u};
//             if(u.y<v.y-eps&&uv.toleft(a)<=0) continue;
//             if(u.y>v.y+eps&&uv.toleft(a)>=0) continue;
//             if(u.y<a.y-eps&&v.y>=a.y-eps) ++cnt;
//             if(u.y>=a.y-eps&&v.y<a.y-eps) --cnt;
//         }
//         return {false,cnt};
//     }
// };
// using ply=polygon<double>;
using a2=std::array<int, 2>;
void slove(){
    int n;
    std::cin>>n;
    std::vector<a2>p;
    for(int i=0;i<n;++i){
        int a,b;
        std::cin>>a>>b;
        p.push_back({a,b});
    }
    auto get=[&](int sta)->int {
        int res=0;
        for(int i=0;i<n;++i){
            int cur=(i+sta)%n,nxt=(i+sta+1)%n,pre=(i-1+sta+n)%n;
            if(p[cur][1]<=p[pre][1]&&p[cur][1]<=p[nxt][1]&&p[nxt][0]>=p[cur][0]){
                // std::cout<<"s: "<<(i+sta)%n<<'\n';
                ++res;
                while(i<n&&p[cur][1]>=p[nxt][1]){
                    ++i;
                    cur=(i+sta)%n,nxt=(i+sta+1)%n;
                }
                // std::cout<<p[cur][0]<<' '<<p[cur][1]<<' '<<p[nxt][0]<<' '<<p[nxt][1]<<'\n';
                // std::cout<<"d: "<<(i+sta)%n<<'\n';
            }
        }
        return res;
    };
    int m=0,y=-1e5;
    for(int i=0;i<n;++i){
        if(p[i][1]>y){
            y=p[i][1];
            m=i;
        }
    }
    int ans=get(m);
    std::cout<<ans<<'\n';
}

signed main(){
#ifdef LOCAL
    std::freopen("in.txt","r",stdin);
    std::freopen("out.txt","w",stdout);
#endif
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int _=1;
    // std::cin>>_;
    for(int i=0;i<_;++i){
        slove();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3496kb

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

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

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'