QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#208833#5155. Faster Than LightJooDdaeWA 1ms3552kbC++201.9kb2023-10-09 21:16:352023-10-09 21:16:35

Judging History

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

  • [2023-10-09 21:16:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3552kb
  • [2023-10-09 21:16:35]
  • 提交

answer

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

struct point {
    ll x, y;

    bool operator < (const point &o) const {
        return tie(x, y) < tie(o.x, o.y);
    }
    point operator - (const point &a)const{
        return {x-a.x, y-a.y};
    }
};

ll cross(point a, point b){
    return a.x * b.y - a.y * b.x;
}

int ccw(point a, point b, point c){
    auto re = cross(b-a, c-a);
    return (re > 0) - (re < 0);
}

bool solve(vector<array<point, 2>> p) {
    sort(p.begin(), p.end());

    vector<point> dh, uh;
    for(auto [u, X] : p) {
        while(dh.size() > 1 && ccw(dh[dh.size()-2], dh.back(), u) >= 0) dh.pop_back();
        dh.push_back(u);
    }

    for(auto &[x, y] : p) swap(x, y);
    sort(p.begin(), p.end());
    for(auto [u, X] : p) {
        while(uh.size() > 1 && ccw(uh[uh.size()-2], uh.back(), u) <= 0) uh.pop_back();
        uh.push_back(u);
    }

    // for(auto [x, y] : dh) cout << x << " " << y << "\n";
    // cout << "----------------------------------\n";
    // for(auto [x, y] : uh) cout << x << " " << y << "\n";


    for(int i=0, j=0;i+1<dh.size();i++) {
        while(j < uh.size() && uh[j].x <= dh[i+1].x) {
            // cout << i << " " << j << " " << ccw(dh[i], dh[i+1], uh[j]) << "\n";
            if(ccw(dh[i], dh[i+1], uh[j]) < 0) return false;
            j++;
        }
    }

    return true;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;

    vector<array<point, 2>> p(n);
    for(auto &[p1, p2] : p) {
        cin >> p1.x >> p1.y;
        cin >> p2.x >> p2.y;
    }
    if(solve(p)) return cout << "possible", 0;

    for(auto &[p1, p2] : p) {
        // p1.x = -p1.x, p2.x = -p2.x;
        swap(p1.x, p2.x);
        // swap(p1, p2);
        // cout << p1.x << " " << p1.y << " " << p2.x << " " << p2.y << "\n";
    }
    cout << (solve(p) ? "possible" : "impossible");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1 3 3 4
2 2 4 3
4 1 5 3
5 2 7 3
6 3 8 4

output:

possible

result:

ok single line: 'possible'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3448kb

input:

4
1 1 2 2
1 3 2 4
3 1 4 2
3 3 4 4

output:

impossible

result:

ok single line: 'impossible'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3484kb

input:

3
1 1 2 2
1 3 2 4
3 3 4 4

output:

possible

result:

ok single line: 'possible'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3552kb

input:

5
0 0 1 999999999
0 999999999 999999999 1000000000
1 0 999999998 1
999999998 0 999999999 999999999
2 999999998 3 999999999

output:

possible

result:

wrong answer 1st lines differ - expected: 'impossible', found: 'possible'