QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207374#5155. Faster Than LightwillowWA 0ms12624kbC++143.5kb2023-10-08 14:51:462023-10-08 14:51:46

Judging History

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

  • [2023-10-08 14:51:46]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:12624kb
  • [2023-10-08 14:51:46]
  • 提交

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;
}

详细

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'