QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#206872 | #5155. Faster Than Light | willow# | WA | 2ms | 12476kb | C++17 | 2.9kb | 2023-10-07 23:35:43 | 2023-10-07 23:35:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const double eps = 1e-9;
int Dcmp(double x) {
return x < -eps ? -1 : x > eps ? 1 : 0;
}
#define x1 asd
#define y1 dsa
#define x2 sad
#define y2 sda
int n, x1[maxn], y1[maxn], x2[maxn], y2[maxn];
struct Point {
int x, y;
Point(int x = 0, int y = 0) : x(x), y(y) {}
Point operator - (const Point &rhs) const {
return Point(x - rhs.x, y - rhs.y);
}
long long operator ^ (const Point &rhs) const {
return 1ll * x * rhs.y - 1ll * y * rhs.x;
}
}up[maxn], dw[maxn], ucon[maxn], dcon[maxn];
int szu, szd;
double Calc(Point s, Point t, double x) {
return s.y + 1. * (t.y - s.y) / (t.x - s.x) * (x - s.x);
}
int main() {
scanf("%d", &n);
int xmin = -1e9, xmax = 1e9, ymin = -1e9, ymax = 1e9;
for(int i = 1; i <= n; ++ i) {
scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
xmin = max(xmin, x1[i]);
ymin = max(ymin, y1[i]);
xmax = min(xmax, x2[i]);
ymax = min(ymax, y2[i]);
}
if(xmin <= xmax || ymin <= ymax) {
return 0 * puts("possible");
}
for(int d = 0; d < 2; ++ d) {
for(int i = 1; i <= n; ++ i) {
up[i] = d ? Point(x1[i], y2[i]) : Point(x2[i], y2[i]);
dw[i] = d ? Point(x2[i], y1[i]) : Point(x1[i], y1[i]);
}
sort(up + 1, up + n + 1, [](Point a, Point b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
});
sort(dw + 1, dw + n + 1, [](Point a, Point b) {
return a.x == b.x ? a.y > b.y : a.x < b.x;
});
szu = szd = 0;
for(int i = 1; i <= n; ++ i) {
if(i > 1 && up[i].x == up[i - 1].x)
continue;
while(szu >= 2 && ((ucon[szu] - ucon[szu - 1]) ^ (up[i] - ucon[szu - 1])) <= 0) {
-- szu;
}
ucon[++ szu] = up[i];
}
for(int i = 1; i <= n; ++ i) {
if(i > 1 && dw[i].x == dw[i - 1].x)
continue;
while(szd >= 2 && ((dcon[szd] - dcon[szd - 1]) ^ (dw[i] - dcon[szd - 1])) >= 0) {
-- szd;
}
dcon[++ szd] = dw[i];
}
int pu = 0, pd = 0, flg = 1;
while(pu < szu && pd < szd) {
Point d0 = dcon[pd], d1 = dcon[pd + 1], u0 = ucon[pu], u1 = ucon[pu + 1];
int lx = max(d0.x, u0.x), rx = min(d1.x, u1.x);
if(lx <= rx) {
if(Dcmp(Calc(u0, u1, lx) - Calc(d0, d1, lx)) >= 0 && Dcmp(Calc(u0, u1, rx) - Calc(d0, d1, rx)) >= 0);
else {
flg = 0;
break;
}
}
if(d1.x < u1.x)
++ pd;
else if(d1.x > u1.x)
++ pu;
else
++ pd, ++ pu;
}
if(flg)
return 0 * puts("possible");
}
puts("impossible");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12240kb
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: 2ms
memory: 12288kb
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: 11556kb
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: 2ms
memory: 12476kb
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: -100
Wrong Answer
time: 0ms
memory: 12212kb
input:
4 0 1 1 1000000000 1 0 999999999 1 999999999 0 1000000000 999999999 2 999999999 999999999 1000000000
output:
impossible
result:
wrong answer 1st lines differ - expected: 'possible', found: 'impossible'