QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#202370#5155. Faster Than Lightsalvator_nosterWA 2ms10532kbC++202.9kb2023-10-05 23:39:542023-10-05 23:39:55

Judging History

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

  • [2023-10-05 23:39:55]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10532kb
  • [2023-10-05 23:39:54]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 200000 + 5;

int N;
struct Point{
    int x, y;
    Point(int a = 0, int b = 0) : x(a), y(b) {}
    inline bool operator < (const Point &comp) const {return x < comp.x || x == comp.x && y < comp.y;}
}p[4][MAX_N];
typedef vector <Point> vp;

vp calc_convex_hull(Point *p) {
    vp res(0);
    sort(p + 1, p + N + 1);
    static int sta[MAX_N];
    int top = 0;
    for (int i = 1; i <= N; i ++) {
        // fprintf(stderr, "i = %d, x = %d, y = %d, top = %d\n", i, p[i].x, p[i].y, top);
        while (top > 1 && 1ll * (p[i].y - p[sta[top]].y) * (p[i].x - p[sta[top - 1]].x) >= 1ll * (p[i].x - p[sta[top]].x) * (p[i].y - p[sta[top - 1]].y)) top --;
        sta[++ top] = i;
    }
    // fprintf(stderr, "top = %d\n", top);
    for (int i = 1; i <= top; i ++) res.push_back(p[sta[i]]);
    top = 0;
    for (int i = N; i > 0; i --) {
        while (top > 1 && 1ll * (p[i].y - p[sta[top]].y) * (p[i].x - p[sta[top - 1]].x) >= 1ll * (p[i].x - p[sta[top]].x) * (p[i].y - p[sta[top - 1]].y)) top --;
        sta[++ top] = i;
    }
    for (int i = 2; i < top; i ++) res.push_back(p[sta[i]]);
    return res;
}

bool check(Point *p1, Point *p2) {
    vp ch1 = calc_convex_hull(p1), ch2 = calc_convex_hull(p2);
    // fprintf(stderr, "ch1 :\n");
    // for (auto [x, y] : ch1) fprintf(stderr, "x = %d, y = %d\n", x, y);
    // fprintf(stderr, "ch2 :\n");
    // for (auto [x, y] : ch2) fprintf(stderr, "x = %d, y = %d\n", x, y);
    // fprintf(stderr, "\n");
    sort(ch1.begin(), ch1.end());
    ch2.push_back(*ch2.begin());
    for (int i = 0, j = ch2.size() - 1, k = 0; i < j && k < ch1.size(); k ++) {
        while (i < j && ch2[i].x <= ch2[i + 1].x && ch2[i + 1].x < ch1[k].x) i ++;
        while (i < j && ch2[j].x <= ch2[j - 1].x && ch2[j - 1].x < ch1[k].x) j --;
        if (i == j) break;
        if (ch2[i].x > ch1[k].x) continue;
        double tmp = (double)(ch1[k].x - ch2[i].x) / (ch2[i + 1].x - ch2[i].x);
        int posu = ceil(tmp * ch2[i + 1].y + (1 - tmp) * ch2[i].y);
        tmp = (double)(ch1[k].x - ch2[j].x) / (ch2[j - 1].x - ch2[j].x);
        int posd = floor(tmp * ch2[j - 1].y + (1 - tmp) * ch2[j].y);
        // fprintf(stderr, "i = %d, j = %d, k = %d, posx = %d, posy = %d, y : (%d, %d)\n", i, j, k, ch1[k].x, ch1[k].y, posd, posu);
        if (posu <= ch1[k].y || ch1[k].y <= posd) continue;
        return false;
    }
    return true;
}

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i ++) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        p[0][i] = Point(x1, y1);
        p[1][i] = Point(x2, y2);
        p[2][i] = Point(x1, y2);
        p[3][i] = Point(x2, y1);
    }
    if (check(p[0], p[1]) || check(p[2], p[3])) puts("possible");
    else puts("impossible");
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 9984kb

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

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

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
Wrong Answer
time: 2ms
memory: 9856kb

input:

5
0 0 1 999999999
0 999999999 999999999 1000000000
1 0 999999998 1
999999998 0 999999999 999999999
2 999999998 3 999999999

output:

possible

result:

wrong answer 1st lines differ - expected: 'impossible', found: 'possible'