QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#208474#5155. Faster Than LightAeren#WA 0ms3888kbC++206.4kb2023-10-09 17:24:252023-10-09 17:24:25

Judging History

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

  • [2023-10-09 17:24:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3888kb
  • [2023-10-09 17:24:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

struct point{
	__int128_t x, y;
	point operator+(const point &p) const{
		return {x + p.x, y + p.y};
	}
	point operator-(const point &p) const{
		return {x - p.x, y - p.y};
	}
	__int128_t operator*(const point &p) const{
		return x * p.x + y * p.y;
	}
	__int128_t operator^(const point &p) const{
		return x * p.y - y * p.x;
	}
	bool operator<(const point &p) const{
		return x != p.x ? x < p.x : y < p.y;
	}
};
bool ccw(const point &p, const point &q, const point &r){
	return (q - p ^ r - p) > 0;
}
bool cw(const point &p, const point &q, const point &r){
	return (q - p ^ r - p) < 0;
}

__int128_t gcd(__int128_t x, __int128_t y){
	if(x < 0){
		x = -x;
	}
	if(y < 0){
		y = -y;
	}
	return y ? gcd(y, x % y) : x;
}

int main()
{
	cin.tie(0)->sync_with_stdio(false);
	cin.exceptions(ios::badbit | ios::failbit);
	int n;
	cin >> n;
	vector<array<__int128_t, 4>> a(n);
	for(auto i = 0; i < n; ++ i){
		for(auto j = 0; j < 4; ++ j){
			int x;
			cin >> x;
			a[i][j] = x;
		}
	}
	auto ok = [&](){
		cout << "possible\n";
		exit(0);
	};
	auto get_lower_hull = [&](deque<point> a){
		sort(a.begin(), a.end(), [&](auto p, auto q){ return p.x != q.x ? p.x < q.x : p.y < q.y; });
		{
			auto temp = a;
			a.clear();
			for(auto p: temp){
				if(a.empty() || a.back().x < p.x){
					a.push_back(p);
				}
			}
		}
		deque<point> hull;
		for(auto p: a){
			while((int)hull.size() >= 2 && !ccw(*next(hull.rbegin()), *hull.rbegin(), p)){
				hull.pop_back();
			}
			hull.push_back(p);
		}
		return hull;
	};
	// < >, < <(x), 
	auto get_upper_hull = [&](deque<point> a){
		sort(a.begin(), a.end(), [&](auto p, auto q){ return p.x != q.x ? p.x < q.x : p.y > q.y; });
		{
			auto temp = a;
			a.clear();
			for(auto p: temp){
				if(a.empty() || a.back().x < p.x){
					a.push_back(p);
				}
			}
		}
		deque<point> hull;
		for(auto p: a){
			while((int)hull.size() >= 2 && !cw(*next(hull.rbegin()), *hull.rbegin(), p)){
				hull.pop_back();
			}
			hull.push_back(p);
		}
		return hull;
	};
	auto eval = [&](point f, __int128_t x){
		return f.x * x + f.y;
	};
	for(auto rep = 2; rep > 0; -- rep){
		deque<point> lower, upper;
		for(auto i = 0; i < n; ++ i){
			lower.push_back({a[i][1] - a[i][0], -a[i][0]});
			upper.push_back({a[i][3] - a[i][2], -a[i][2]});
		}
		lower = get_lower_hull(lower);
		upper = get_upper_hull(upper);
		for(auto &[x, y]: lower){
			y = -y;
		}
		// cerr << "Lower ";
		// for(auto &[x, y]: lower){
		// 	cerr << "{" << x << ", " << y << "}";
		// }
		// cerr << endl;
		while((int)lower.size() >= 2 && eval(lower[0], 0) <= eval(lower[1], 0)){
			lower.pop_front();
		}
		while((int)lower.size() >= 2 && eval(*lower.rbegin(), 1) <= eval(*next(lower.rbegin()), 1)){
			lower.pop_back();
		}
		for(auto &[x, y]: upper){
			y = -y;
		}
		reverse(upper.begin(), upper.end());
		// cerr << "Upper ";
		// for(auto [x, y]: upper){
		// 	cerr << "{" << x << ", " << y << "}";
		// }
		// cerr << endl;
		while((int)upper.size() >= 2 && eval(upper[0], 0) >= eval(upper[1], 0)){
			upper.pop_front();
		}
		while((int)upper.size() >= 2 && eval(*upper.rbegin(), 1) >= eval(*next(upper.rbegin()), 1)){
			upper.pop_back();
		}
		// cerr << "Lower ";
		// for(auto &[x, y]: lower){
		// 	cerr << "{" << x << ", " << y << "}";
		// }
		// cerr << endl;
		// cerr << "Upper ";
		// for(auto [x, y]: upper){
		// 	cerr << "{" << x << ", " << y << "}";
		// }
		// cerr << endl;
		using Frac = array<__int128_t, 2>;
		auto reduce = [&](Frac x)->Frac{
			auto g = gcd(x[0], x[1]);
			return {x[0] / g, x[1] / g};
		};
		auto inter = [&](point f, point g){
			assert(f.x != g.x);
			Frac x{
				f.y - g.y,
				g.x - f.x
			};
			if(x[1] < 0){
				x[0] = -x[0];
				x[1] = -x[1];
			}
			Frac y{
				f.x * x[0] + f.y * x[1],
				x[1]
			};
			return array{reduce(x), reduce(y)};
		};
		using pF = array<Frac, 2>;
		vector<pF> interlow{pF{{{0, 1}, {lower[0].y, 1}}}};
		for(auto i = 0; i + 1 < (int)lower.size(); ++ i){
			interlow.push_back(inter(lower[i], lower[i + 1]));
		}
		interlow.push_back({{{1, 1}, {lower.back().x + lower.back().y, 1}}});
		vector<pF> interhigh{pF{{{0, 1}, {upper[0].y, 1}}}};
		for(auto i = 0; i + 1 < (int)upper.size(); ++ i){
			interhigh.push_back(inter(upper[i], upper[i + 1]));
		}
		interhigh.push_back({{{1, 1}, {upper.back().x + upper.back().y, 1}}});
		auto cmp = [&](Frac x, Frac y){
			return x[0] * y[1] < x[1] * y[0];
		};
		auto plus = [&](Frac x, Frac y){
			return reduce(Frac{x[0] * y[1] + x[1] * y[0], x[1] * y[1]});
		};
		auto minus = [&](Frac x, Frac y){
			return reduce(Frac{x[0] * y[1] - x[1] * y[0], x[1] * y[1]});
		};
		auto mul = [&](Frac x, Frac y){
			return reduce(Frac{x[0] * y[0], x[1] * y[1]});
		};
		auto div = [&](Frac x, Frac y){
			assert(y[0] > 0);
			return reduce(Frac{x[0] * y[1], x[1] * y[0]});
		};
		auto cut = [&](pF p, pF q, Frac x){
			return div(
				plus(
					mul(p[1], minus(q[0], x)),
					mul(q[1], minus(x, p[0]))
				),
				minus(q[0], p[0])
			);
		};
		// cerr << "Interlow ";
		// for(auto [x, y]: interlow){
		// 	cerr << "{" << (long long)x[0] << "/" << (long long)x[1] << "," << (long long)y[0] << "/" << (long long)y[1] << "}";
		// }
		// cerr << endl;
		// cerr << "Interhigh ";
		// for(auto [x, y]: interhigh){
		// 	cerr << "{" << (long long)x[0] << "/" << (long long)x[1] << "," << (long long)y[0] << "/" << (long long)y[1] << "}";
		// }
		// cerr << endl;
		for(auto i = 0, j = 0; i + 1 < (int)interlow.size() || j + 1 < (int)interhigh.size(); ){
			if(j + 1 == (int)interhigh.size() || i + 1 < (int)interlow.size() && cmp(interlow[i][0], interhigh[j][0])){
				auto y = cut(interlow[i], interlow[i + 1], interhigh[j][0]);
				// cerr << "First " << i << " " << j << " " << (long long)y[0] << " " << (long long)y[1] << endl;
				if(!cmp(interhigh[j][1], y)){
					ok();
				}
				++ i;
			}
			else{
				auto y = cut(interhigh[j], interhigh[j + 1], interlow[i][0]);
				// cerr << "Second " << i << " " << j << " " << (long long)y[0] << " " << (long long)y[1] << endl;
				if(!cmp(y, interlow[i][1])){
					ok();
				}
				++ j;
			}
		}
		// cerr << endl;
		const int mx = 1e9;
		for(auto i = 0; i < n; ++ i){
			a[i][0] = mx - a[i][0];
			a[i][2] = mx - a[i][2];
			swap(a[i][0], a[i][2]);
			assert(a[i][0] < a[i][2]);
			assert(a[i][1] < a[i][3]);
		}
	}
	cout << "impossible\n";
	return 0;
}

詳細信息

Test #1:

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

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

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

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

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'