QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#206904#5155. Faster Than LightwillowRE 2ms12320kbC++173.4kb2023-10-08 00:03:152023-10-08 00:03:15

Judging History

你现在查看的是最新测评结果

  • [2023-10-08 00:03:15]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:12320kb
  • [2023-10-08 00:03:15]
  • 提交

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

output:


result: