QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#207374 | #5155. Faster Than Light | willow | WA | 0ms | 12624kb | C++14 | 3.5kb | 2023-10-08 14:51:46 | 2023-10-08 14:51:46 |
Judging History
answer
#include <bits/stdc++.h>
#define y1 wow
using namespace std;
typedef long long LL;
typedef long double LD;
const int MAXN = 200005;
template <typename T> inline void read(T &WOW) {
T x = 0, flag = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') flag = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
WOW = flag * x;
}
int n, x1[MAXN], y1[MAXN], x2[MAXN], y2[MAXN];
struct Point {
LL x, y;
Point(LL _x = 0, LL _y = 0): x(_x), y(_y) {}
Point operator + (const Point &rhs) const {
return Point(x + rhs.x, y + rhs.y);
}
Point operator - (const Point &rhs) const {
return Point(x - rhs.x, y - rhs.y);
}
LL operator * (const Point &rhs) const {
return x * rhs.x + y * rhs.y;
}
LL operator ^ (const Point &rhs) const {
return x * rhs.y - y * rhs.x;
}
inline LL len2() {
return x * x + y * y;
}
} p[MAXN], q[MAXN];
void solve() {
read(n);
int mnx2 = 2e9, mxx1 = -2e9, mny2 = 2e9, mxy1 = -2e9;
for (int i = 1; i <= n; ++i) {
read(x1[i]); read(y1[i]); read(x2[i]); read(y2[i]);
mxx1 = max(mxx1, x1[i]);
mnx2 = min(mnx2, x2[i]);
mxy1 = max(mxy1, y1[i]);
mny2 = min(mny2, y2[i]);
}
if (n <= 2 || mxx1 <= mnx2 || mxy1 <= mny2) {
puts("possible");
return;
}
for (int T = 0; T <= 2; ++T) {
for (int i = 1; i <= n; ++i) {
if (T == 0) {
p[i] = Point(x1[i], y2[i]); //up
q[i] = Point(x2[i], y1[i]); //dn
} else {
p[i] = Point(x2[i], y2[i]); //up
q[i] = Point(x1[i], y1[i]); //dn
}
}
sort(p + 1, p + n + 1, [](Point u, Point v) {
return u.x == v.x? u.y < v.y : u.x < v.x;
});
int tp = 1;
for (int i = 2; i <= n; ++i) {
if (p[i].x == p[tp].x) continue;
while (tp > 1 && ((p[i] - p[tp - 1]) ^ (p[tp] - p[tp - 1])) >= 0) {
--tp;
}
p[++tp] = p[i];
}
sort(q + 1, q + n + 1, [](Point u, Point v) {
return u.x == v.x? u.y > v.y : u.x < v.x;
});
int tq = 1;
for (int i = 2; i <= n; ++i) {
if (q[i].x == q[tp].x) continue;
while (tq > 1 && ((q[i] - q[tq - 1]) ^ (q[tq] - q[tq - 1])) <= 0) {
--tq;
}
q[++tq] = q[i];
}
bool flag = 0;
for (int i = 1, j = 1; i <= tp; ++i) {
if (p[i].x < q[1].x || p[i].x > q[tq].x) continue;
while (p[i].x > q[j].x) {
++j;
}
if (p[i].x == q[j].x) {
flag |= (p[i].y < q[j].y);
} else {
flag |= (((q[j] - q[j - 1]) ^ (p[i] - q[j - 1])) < 0);
}
}
for (int i = 1, j = 1; i <= tq; ++i) {
if (q[i].x < p[1].x || q[i].x > p[tp].x) continue;
while (q[i].x > p[j].x) {
++j;
}
if (q[i].x == p[j].x) {
flag |= (q[i].y > p[j].y);
} else {
flag |= (((p[j] - p[j - 1]) ^ (q[i] - p[j - 1])) > 0);
}
}
if (!flag) {
puts("possible");
return;
}
}
puts("impossible");
}
int main() {
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11576kb
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: 12624kb
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: 11636kb
input:
3 1 1 2 2 1 3 2 4 3 3 4 4
output:
possible
result:
ok single line: 'possible'
Test #4:
score: 0
Accepted
time: 0ms
memory: 12280kb
input:
5 0 0 1 999999999 0 999999999 999999999 1000000000 1 0 999999998 1 999999998 0 999999999 999999999 2 999999998 3 999999999
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 0ms
memory: 11280kb
input:
4 0 1 1 1000000000 1 0 999999999 1 999999999 0 1000000000 999999999 2 999999999 999999999 1000000000
output:
possible
result:
ok single line: 'possible'
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 11764kb
input:
3 0 0 1 1000000000 2 0 999999999 1 2 999999999 999999999 1000000000
output:
possible
result:
wrong answer 1st lines differ - expected: 'impossible', found: 'possible'