QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#206904 | #5155. Faster Than Light | willow | RE | 2ms | 12320kb | C++17 | 3.4kb | 2023-10-08 00:03:15 | 2023-10-08 00:03:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
#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;
struct Frac {
__int128 x, y;
Frac(__int128 x = 0, __int128 y = 1) : x(x), y(y) {
__int128 g = __gcd(x, y);
// cerr << (long long)g << endl;
x /= g, y /= g;
}
bool operator < (const Frac &rhs) const {
if(x / y < rhs.x / rhs.y)
return 1;
if(x / y > rhs.x / rhs.y)
return 0;
return (x % y) * rhs.y < y * (rhs.x % rhs.y);
}
Frac operator + (const Frac &rhs) const {
return Frac(x * rhs.y + y * rhs.x, y * rhs.y);
}
};
Frac Calc(Point s, Point t, int x) {
// cerr << s.x << " " << s.y << " " << t.x << " " << t.y << endl;
assert(t.x != s.x);
return Frac(s.y, 1) + Frac(1ll * (t.y - s.y) * (x - s.x), (t.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(Calc(u0, u1, lx) < Calc(d0, d1, lx) || Calc(u0, u1, rx) < Calc(d0, d1, rx)) {
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: 11124kb
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: 11844kb
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: 2ms
memory: 12320kb
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
Runtime Error
input:
5 0 0 1 999999999 0 999999999 999999999 1000000000 1 0 999999998 1 999999998 0 999999999 999999999 2 999999998 3 999999999