QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#202370 | #5155. Faster Than Light | salvator_noster | WA | 2ms | 10532kb | C++20 | 2.9kb | 2023-10-05 23:39:54 | 2023-10-05 23:39:55 |
Judging History
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'