QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#149396 | #5155. Faster Than Light | LaStataleBlue | WA | 0ms | 1696kb | C++14 | 1.7kb | 2023-08-24 15:27:00 | 2023-08-24 15:27:01 |
Judging History
answer
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
constexpr int MAXN = 2e5;
struct Point {
int x, y;
};
struct Rectangle {
Point a, b;
};
struct Rational {
int a, b;
bool operator<(const Rational &o) const { return (ll)a * o.b < (ll)b * o.a; }
};
template <typename T> struct Range {
T a, b;
bool intersect(const Range<T> &o) {
if (b < o.a || o.b < a)
return false;
a = max(a, o.a);
b = min(b, o.b);
return true;
}
};
int N;
Rectangle v[MAXN];
void flip_xy() {
for (int i = 0; i < N; i++) {
swap(v[i].a.x, v[i].a.y);
swap(v[i].b.x, v[i].b.y);
}
}
void check() {
for (int i = 0; i < N; i++) {
Rectangle &r = v[i];
if (r.a.x > r.b.x)
swap(r.a, r.b);
if (r.a.y < r.b.y)
swap(r.a.y, r.b.y);
}
auto get_shadow = [](const Rectangle &r) -> Range<int> {
return Range<int>{r.b.y - r.b.x, r.a.y};
};
Range<int> shadow = get_shadow(v[0]);
for (int i = 1; i < N; i++)
if (!shadow.intersect(get_shadow(v[i])))
return;
auto get_slope = [](const Point &a, const Point &b) -> Rational {
return {a.y - b.y, a.x - b.x};
};
Point bot = {0, shadow.a};
Point top = {0, shadow.b};
Range<Rational> slopes = {{0, 1}, {1, 1}};
for (int i = 0; i < N; i++) {
const Range<Rational> r = {get_slope(v[i].b, top), get_slope(v[i].a, bot)};
if(!slopes.intersect(r))
return;
}
printf("possible\n");
exit(0);
}
int main() {
scanf("%d", &N);
int maxx = 0;
for (int i = 0; i < N; i++) {
scanf("%d %d %d %d", &v[i].a.x, &v[i].a.y, &v[i].b.x, &v[i].b.y);
maxx = max({maxx, v[i].a.x, v[i].b.x});
}
check();
flip_xy();
check();
for (int i = 0; i < N; i++) {
v[i].a.y = -v[i].a.y + maxx;
v[i].b.y = -v[i].b.y + maxx;
}
check();
flip_xy();
check();
printf("impossible\n");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 1620kb
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: 1696kb
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: 1652kb
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: 1680kb
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'