QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#208833 | #5155. Faster Than Light | JooDdae | WA | 1ms | 3552kb | C++20 | 1.9kb | 2023-10-09 21:16:35 | 2023-10-09 21:16:35 |
Judging History
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'