QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#206893#5155. Faster Than Lightwillow#WA 2ms12000kbC++172.9kb2023-10-07 23:51:522023-10-07 23:51:53

Judging History

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

  • [2023-10-07 23:51:53]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12000kb
  • [2023-10-07 23:51:52]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const __float128 eps = 1e-12;
__float128 one = 1;
int Dcmp(__float128 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;
__float128 Calc(Point s, Point t, __float128 x) {
    return s.y + one * (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) {
                    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");
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 11928kb

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: 12000kb

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: 11324kb

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: 11464kb

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: 11836kb

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'