QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#149396#5155. Faster Than LightLaStataleBlueWA 0ms1696kbC++141.7kb2023-08-24 15:27:002023-08-24 15:27:01

Judging History

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

  • [2023-08-24 15:27:01]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:1696kb
  • [2023-08-24 15:27:00]
  • 提交

answer

#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
constexpr int MAXN = 2e5;

struct Point {
	int x, y;
};

struct Rectangle {
	Point a, b;
};

struct Rational {
	int a, b;
	bool operator<(const Rational &o) const { return (ll)a * o.b < (ll)b * o.a; }
};

template <typename T> struct Range {
	T a, b;
	bool intersect(const Range<T> &o) {
		if (b < o.a || o.b < a)
			return false;
		a = max(a, o.a);
		b = min(b, o.b);
		return true;
	}
};

int N;
Rectangle v[MAXN];

void flip_xy() {
	for (int i = 0; i < N; i++) {
		swap(v[i].a.x, v[i].a.y);
		swap(v[i].b.x, v[i].b.y);
	}
}

void check() {
	for (int i = 0; i < N; i++) {
		Rectangle &r = v[i];
		if (r.a.x > r.b.x)
			swap(r.a, r.b);
		if (r.a.y < r.b.y)
			swap(r.a.y, r.b.y);
	}

	auto get_shadow = [](const Rectangle &r) -> Range<int> {
		return Range<int>{r.b.y - r.b.x, r.a.y};
	};
	Range<int> shadow = get_shadow(v[0]);
	for (int i = 1; i < N; i++)
		if (!shadow.intersect(get_shadow(v[i])))
			return;

	auto get_slope = [](const Point &a, const Point &b) -> Rational {
		return {a.y - b.y, a.x - b.x};
	};
	Point bot = {0, shadow.a};
	Point top = {0, shadow.b};
	Range<Rational> slopes = {{0, 1}, {1, 1}};
	for (int i = 0; i < N; i++) {
		const Range<Rational> r = {get_slope(v[i].b, top), get_slope(v[i].a, bot)};
		if(!slopes.intersect(r))
			return;
	}

	printf("possible\n");
	exit(0);
}

int main() {
	scanf("%d", &N);
	int maxx = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d %d %d %d", &v[i].a.x, &v[i].a.y, &v[i].b.x, &v[i].b.y);
		maxx = max({maxx, v[i].a.x, v[i].b.x});
	}

	check();

	flip_xy();
	check();

	for (int i = 0; i < N; i++) {
		v[i].a.y = -v[i].a.y + maxx;
		v[i].b.y = -v[i].b.y + maxx;
	}
	check();

	flip_xy();
	check();

	printf("impossible\n");
	return 0;
}

详细

Test #1:

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

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

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

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: 0ms
memory: 1680kb

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'