QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#708223#5426. Drain the Water TankRighttWA 0ms3752kbC++141.5kb2024-11-03 20:33:242024-11-03 20:33:25

Judging History

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

  • [2024-11-03 20:33:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3752kb
  • [2024-11-03 20:33:24]
  • 提交

answer

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
using ll = long long;

#define x first 
#define y second 

using pt = pair<int, int>;

bool check(pt a, pt b, pt c){
    int x1 = b.x - a.x, x2 = c.x - b.x;
    int y1 = b.y - a.y, y2 = c.y - b.y;
    return ((x1 >= 0) && (y1 < 0)) && ((x2 >= 0) && (y2 > 0));
}

bool c2(pt a, pt b, pt d, pt c){
    int x1 = b.x - a.x, y1 = b.y - a.y;
    int x2 = c.x - d.x, y2 = c.y - d.y;
    return ((y1 < 0)) && (y2 > 0);
}

void solve(){
    int n;
    cin >> n;
    vector<pair<int, int>> v(2 * n + 1);
    for (int i = 0; i < n; i ++ ){
        cin >> v[i].x >> v[i].y;
        v[i+n] = v[i];
    }
    set<pt> ans;
    for (int i = 0; i + 2 < 2 * n; i ++ ){
        if (check(v[i], v[i+1], v[i + 2])){
            ans.insert(v[i+1]);
        }
    }
    //判断水平
    int num = 0;
    map<pt, int> st;
    for (int i = 1; i + 2 < 2 * n; i ++ ){
        int j = i;
        while (j + 1 < 2 * n && v[j + 1].y == v[i].y){
            j ++;
        }
        if (i == j || v[i].y == v[i-1].y || j == 2 * n - 1 || v[j].y == v[j+1].y){
            continue;
        }
        if (st[v[i]]) continue;
        if (c2(v[i-1], v[i], v[j], v[j+1])){
            for (int k = i; k <= j; k ++ ) st[v[k]] = 1;
            i = j;
            num ++;
        }
    }
    cout << ans.size() + num;
}

signed main(){
    IOS;
    int t = 1;
//		cin >> t;
    while (t -- ){
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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'