QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#208472 | #5155. Faster Than Light | Aeren# | WA | 0ms | 3688kb | C++20 | 6.3kb | 2023-10-09 17:21:11 | 2023-10-09 17:21:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct point{
long long x, y;
point operator+(const point &p) const{
return {x + p.x, y + p.y};
}
point operator-(const point &p) const{
return {x - p.x, y - p.y};
}
long long operator*(const point &p) const{
return x * p.x + y * p.y;
}
long long operator^(const point &p) const{
return x * p.y - y * p.x;
}
bool operator<(const point &p) const{
return x != p.x ? x < p.x : y < p.y;
}
};
bool ccw(const point &p, const point &q, const point &r){
return (q - p ^ r - p) > 0;
}
bool cw(const point &p, const point &q, const point &r){
return (q - p ^ r - p) < 0;
}
__int128_t gcd(__int128_t x, __int128_t y){
if(x < 0){
x = -x;
}
if(y < 0){
y = -y;
}
return y ? gcd(y, x % y) : x;
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
cin.exceptions(ios::badbit | ios::failbit);
int n;
cin >> n;
vector<array<long long, 4>> a(n);
for(auto i = 0; i < n; ++ i){
for(auto j = 0; j < 4; ++ j){
cin >> a[i][j];
}
}
auto ok = [&](){
cout << "possible\n";
exit(0);
};
auto get_lower_hull = [&](deque<point> a){
sort(a.begin(), a.end(), [&](auto p, auto q){ return p.x != q.x ? p.x < q.x : p.y < q.y; });
{
auto temp = a;
a.clear();
for(auto p: temp){
if(a.empty() || a.back().x < p.x){
a.push_back(p);
}
}
}
deque<point> hull;
for(auto p: a){
while((int)hull.size() >= 2 && !ccw(*next(hull.rbegin()), *hull.rbegin(), p)){
hull.pop_back();
}
hull.push_back(p);
}
return hull;
};
auto get_upper_hull = [&](deque<point> a){
sort(a.begin(), a.end(), [&](auto p, auto q){ return p.x != q.x ? p.x < q.x : p.y > q.y; });
{
auto temp = a;
a.clear();
for(auto p: temp){
if(a.empty() || a.back().x < p.x){
a.push_back(p);
}
}
}
deque<point> hull;
for(auto p: a){
while((int)hull.size() >= 2 && !cw(*next(hull.rbegin()), *hull.rbegin(), p)){
hull.pop_back();
}
hull.push_back(p);
}
return hull;
};
auto eval = [&](point f, __int128_t x){
return f.x * x + f.y;
};
for(auto rep = 2; rep > 0; -- rep){
deque<point> lower, upper;
for(auto i = 0; i < n; ++ i){
lower.push_back({a[i][1] - a[i][0], -a[i][0]});
upper.push_back({a[i][3] - a[i][2], -a[i][2]});
}
lower = get_lower_hull(lower);
upper = get_upper_hull(upper);
for(auto &[x, y]: lower){
y = -y;
}
// cerr << "Lower ";
// for(auto &[x, y]: lower){
// cerr << "{" << x << ", " << y << "}";
// }
// cerr << endl;
while((int)lower.size() >= 2 && eval(lower[0], 0) <= eval(lower[1], 0)){
lower.pop_front();
}
while((int)lower.size() >= 2 && eval(*lower.rbegin(), 1) <= eval(*next(lower.rbegin()), 1)){
lower.pop_back();
}
for(auto &[x, y]: upper){
y = -y;
}
reverse(upper.begin(), upper.end());
// cerr << "Upper ";
// for(auto [x, y]: upper){
// cerr << "{" << x << ", " << y << "}";
// }
// cerr << endl;
while((int)upper.size() >= 2 && eval(upper[0], 0) >= eval(upper[1], 0)){
upper.pop_front();
}
while((int)upper.size() >= 2 && eval(*upper.rbegin(), 1) >= eval(*next(upper.rbegin()), 1)){
upper.pop_back();
}
// cerr << "Lower ";
// for(auto &[x, y]: lower){
// cerr << "{" << x << ", " << y << "}";
// }
// cerr << endl;
// cerr << "Upper ";
// for(auto [x, y]: upper){
// cerr << "{" << x << ", " << y << "}";
// }
// cerr << endl;
using Frac = array<__int128_t, 2>;
auto reduce = [&](Frac x)->Frac{
auto g = gcd(x[0], x[1]);
return {x[0] / g, x[1] / g};
};
auto inter = [&](point f, point g){
assert(f.x != g.x);
Frac x{
f.y - g.y,
g.x - f.x
};
if(x[1] < 0){
x[0] = -x[0];
x[1] = -x[1];
}
Frac y{
f.x * x[0] + f.y * x[1],
x[1]
};
return array{reduce(x), reduce(y)};
};
using pF = array<Frac, 2>;
vector<pF> interlow{pF{{{0, 1}, {lower[0].y, 1}}}};
for(auto i = 0; i + 1 < (int)lower.size(); ++ i){
interlow.push_back(inter(lower[i], lower[i + 1]));
}
interlow.push_back({{{1, 1}, {lower.back().x + lower.back().y, 1}}});
vector<pF> interhigh{pF{{{0, 1}, {upper[0].y, 1}}}};
for(auto i = 0; i + 1 < (int)upper.size(); ++ i){
interhigh.push_back(inter(upper[i], upper[i + 1]));
}
interhigh.push_back({{{1, 1}, {upper.back().x + upper.back().y, 1}}});
auto cmp = [&](Frac x, Frac y){
return x[0] * y[1] < x[1] * y[0];
};
auto plus = [&](Frac x, Frac y){
return reduce(Frac{x[0] * y[1] + x[1] * y[0], x[1] * y[1]});
};
auto minus = [&](Frac x, Frac y){
return reduce(Frac{x[0] * y[1] - x[1] * y[0], x[1] * y[1]});
};
auto mul = [&](Frac x, Frac y){
return reduce(Frac{x[0] * y[0], x[1] * y[1]});
};
auto div = [&](Frac x, Frac y){
assert(y[0] > 0);
return reduce(Frac{x[0] * y[1], x[1] * y[0]});
};
auto cut = [&](pF p, pF q, Frac x){
return div(
plus(
mul(p[1], minus(q[0], x)),
mul(q[1], minus(x, p[0]))
),
minus(q[0], p[0])
);
};
// cerr << "Interlow ";
// for(auto [x, y]: interlow){
// cerr << "{" << (long long)x[0] << "/" << (long long)x[1] << "," << (long long)y[0] << "/" << (long long)y[1] << "}";
// }
// cerr << endl;
// cerr << "Interhigh ";
// for(auto [x, y]: interhigh){
// cerr << "{" << (long long)x[0] << "/" << (long long)x[1] << "," << (long long)y[0] << "/" << (long long)y[1] << "}";
// }
// cerr << endl;
for(auto i = 0, j = 0; i + 1 < (int)interlow.size() || j + 1 < (int)interhigh.size(); ){
if(j + 1 == (int)interhigh.size() || i + 1 < (int)interlow.size() && cmp(interlow[i][0], interhigh[j][0])){
auto y = cut(interlow[i], interlow[i + 1], interhigh[j][0]);
// cerr << "First " << i << " " << j << " " << (long long)y[0] << " " << (long long)y[1] << endl;
if(!cmp(interhigh[j][1], y)){
ok();
}
++ i;
}
else{
auto y = cut(interhigh[j], interhigh[j + 1], interlow[i][0]);
// cerr << "Second " << i << " " << j << " " << (long long)y[0] << " " << (long long)y[1] << endl;
if(!cmp(y, interlow[i][1])){
ok();
}
++ j;
}
}
// cerr << endl;
const int mx = 1e9;
for(auto i = 0; i < n; ++ i){
a[i][0] = mx - a[i][0];
a[i][2] = mx - a[i][2];
swap(a[i][0], a[i][2]);
}
}
cout << "impossible\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3680kb
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: 0ms
memory: 3612kb
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: 3624kb
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: 3688kb
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'