QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#51620#985. Attractions On PlaneYaoBIGWA 3ms4076kbC++176.2kb2022-10-03 03:31:322022-10-03 03:31:34

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-03 03:31:34]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:4076kb
  • [2022-10-03 03:31:32]
  • 提交

answer

#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }
using namespace std;

template<class A, class B> string to_string(pair<A, B> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string) s); }
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(bool x) { return x ? "true" : "false"; }
template<class A> string to_string(A v) {
	bool first = 1;
	string res = "{";
	for (const auto &x: v) {
		if (!first) res += ", ";
		first = 0;
		res += to_string(x);
	}
	res += "}";
	return res;
}
template<class A, class B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }

void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(H h, T... t) {
	cerr << " " << to_string(h);
	debug_out(t...);
}
#ifndef ONLINE_JUDGE
	#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
	#define debug(...) if(0) puts("No effect.")
#endif


using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

template<class T>
struct Point {
	using P = Point<T>;
	using type = T;
	static constexpr T eps = 1e-9;
	static constexpr bool isInt = is_integral_v<T>;
	static int sgn(T x) { return (x > eps) - (x < -eps); }
	static int cmp(T x, T y) { return sgn(x - y); }

	T x, y;
	P operator +(P a) const { return P{x + a.x, y + a.y}; }
	P operator -(P a) const { return P{x - a.x, y - a.y}; }
	P operator *(T a) const { return P{x * a, y * a}; }
	P operator /(T a) const { return P{x / a, y / a}; }
	bool operator ==(P a) const { return cmp(x, a.x) == 0 && cmp(y, a.y) == 0; }
	T len() const { return sqrt(x * x + y * y); }

	T cross(P b) const { return x * b.y - y * b.x; }

	bool is_upper() const { return y >eps || (sgn(y) == 0 && x < -eps); }
	static int argcmp(P a, P b) {
		if (a.is_upper() != b.is_upper()) return cmp(a.is_upper(), b.is_upper());
		return sgn(b.cross(a));
	}
	T dis_to_line(P a, P b) const {
		if (isInt) return (*this - a).cross(b - a);
		else if (a == b) return 0;
		else return (*this - a).cross(b - a) / (b - a).len();
	}
};

template<class P>
struct HalfPlane {
	P a, b;
	int ind;
	P dir() const { return b - a; }
	bool include(P p) const { return p.dis_to_line(a, b) < -P::eps; }
	bool operator <(const HalfPlane &rhs) const { 
		return P::argcmp(dir(), rhs.dir()) < 0;
	}
	pair<bool, P> capLL(const HalfPlane &rhs) const {
		auto s0 = (a - rhs.a).cross(rhs.dir());
		auto s1 = (b - rhs.a).cross(rhs.dir());
		if (P::cmp(s0, s1) == 0) return {false, P{}};
		return {true, (b * s0 - a * s1) / (s0 - s1)};
	}
};

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	using T = long double;
	using P = Point<T>;
	using HP = HalfPlane<P>;

	int n; T X; cin >> n >> X;
	vector<P> as(n), bs(n);
	rep(i, 0, n - 1) {
		T x, y, w, h; cin >> x >> y >> w >> h;
		as[i] = {x, y};
		bs[i] = {x + w, y};
	}

	using node = pair<T, T>;
	auto getline = [&](P a) -> node {
		auto [x, y] = a;
		T k = -2 * x;
		T b = x * x + y * y;
		return node{k, b};
	};
	map<node, int> mp;
	revrep(i, 0, n - 1) {
		mp[getline(as[i])] = i;
		mp[getline(bs[i])] = i;
	}
	vector<HP> hps;
	for (auto [nd, ind]: mp) {
		auto [k, b] = nd;
		hps.push_back(HP{P{1, k + b}, P{0, b}, ind});
	}
	auto Samedir = [](HP &r, HP &s) { return (r < s || s < r) == 0; };
	sort(all(hps), [&](HP &r, HP &s) { return Samedir(r, s) ? s.include(r.a) : r < s; });
	auto check = [](HP &w, HP &r, HP &s) {
		auto [res, p] = r.capLL(s);
		if (res == 0) return false;
		return w.include(p);
	};
	
	deque<HP> q;

	rep(i, 0, sz(hps) - 1) {
		if (i && Samedir(hps[i], hps[i - 1])) continue;
		while (sz(q) > 1 && !check(hps[i], q.end()[-2], q.end()[-1])) q.pop_back();
		q.push_back(hps[i]);
	}
	while (sz(q) > 1) {
		auto [ok, p] = q[0].capLL(q[1]);
		assert(ok);
		if (P::cmp(p.x, X) >= 0) q.pop_back();
		else break;
	}
	reverse(all(q));
	while (sz(q) > 1) {
		auto [ok, p] = q[0].capLL(q[1]);
		assert(ok);
		if (P::cmp(p.x, 0) <= 0) q.pop_front();
		else break;
	}

	vector<tuple<T, int, T, T>> segs;
	rep(i, 0, n - 1) {
		T y = as[i].y;
		T l = as[i].x;
		T r = bs[i].x;
		segs.emplace_back(y * y, i, l, r);
	}
	sort(all(segs));
	reverse(all(segs));
	set<tuple<T, T, T, int>> S;
	for (auto [y, ind, l, r]: segs) {
		while (1) {
			auto it = S.lower_bound({l, T{-1}, T{}, -1});
			if (it == S.end()) break;
			auto [a, b, y, id] = *it;
			if (a >= r) break;
			S.erase(it);
			if (b > r) S.emplace(r, b, y, id); 
		}
		while (1) {
			auto it = S.lower_bound({l, T{-1}, T{}, -1});
			if (it == S.begin()) break;
			it--;
			auto [a, b, y, id] = *it;
			if (b <= l) break;
			S.erase(it);
			S.emplace(a, l, y, id);
			if (b > r) S.emplace(r, b, y, id);
		}
		S.emplace(l, r, y, ind);
	}
	vector<T> nums{0};
	rep(i, 0, sz(q) - 2) {
		auto [ok, p] = q[i].capLL(q[i + 1]);
		assert(ok);
		nums.push_back(p.x);
	}
	nums.push_back(X);
	vector<T> ans(n);
	rep(i, 0, sz(q) - 1) {
		auto ind = q[i].ind;
		ans[ind] += nums[i + 1] - nums[i];
	}
	for (auto [l, r, y, id]: S) {
		auto pos = upper_bound(all(nums), l) - nums.begin() - 1;	
		while (pos < sz(q) && nums[pos] < r) {
			auto L = max(l, nums[pos]);
			auto R = min(r, nums[pos + 1]);
			auto E = q[pos].a;
			auto D = q[pos].b;
			auto ind = q[pos].ind;
			auto k = E.y - D.y;
			auto b = D.y;
			T A = 1;
			T B = k;
			T C = b - y;
			auto delta = B * B - 4 * A * C;
			if (delta <= 0) {
				ans[ind] -= R - L;
				ans[id] += R - L;
			} else {
				auto x1 = (-B - sqrt(delta)) / (A * 2); 
				auto x2 = (-B + sqrt(delta)) / (A * 2); 
				chmax(x1, L);
				chmin(x2, R);
				T len = x1 < x2 ? x2 - x1 : 0;
				ans[ind] -= R - L - len;
				ans[id] += R - L - len;
			}
			pos++;
		}
	}
	for (auto x: ans) {
		printf("%.10f\n", (double) (x / X * 100));
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3940kb

input:

2 10
1 2 5 1
2 1 1 5

output:

52.6794919243
47.3205080757

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

4 7
1 3 0 0
3 4 0 0
5 5 0 0
3 4 0 0

output:

53.5714285714
35.7142857143
10.7142857143
0.0000000000

result:

ok 4 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 3900kb

input:

4 7
1 3 0 0
3 4 0 0
5 5 0 0
3 4 0 0

output:

53.5714285714
35.7142857143
10.7142857143
0.0000000000

result:

ok 4 numbers

Test #4:

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

input:

2 10
1 2 5 1
2 1 1 5

output:

52.6794919243
47.3205080757

result:

ok 2 numbers

Test #5:

score: 0
Accepted
time: 2ms
memory: 3732kb

input:

4 7
1 3 0 0
3 4 0 0
5 5 0 0
3 4 0 0

output:

53.5714285714
35.7142857143
10.7142857143
0.0000000000

result:

ok 4 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

1 526993
64 7 0 0

output:

100.0000000000

result:

ok found '100.0000000', expected '100.0000000', error '0.0000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3900kb

input:

2 306235
19 8 0 0
21 6 0 0

output:

0.0042451059
99.9957548941

result:

ok 2 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

3 795677
34 3 0 0
56 5 0 0
48 7 0 0

output:

0.0053323863
99.9936532035
0.0010144102

result:

ok 3 numbers

Test #9:

score: 0
Accepted
time: 1ms
memory: 3860kb

input:

495 368130
723082 376716 0 0
723082 376716 0 0
723082 376716 0 0
723082 376716 0 0
723082 376716 0 0
723082 376716 0 0
723082 376716 0 0
723082 376716 0 0
723082 376716 0 0
723082 376716 0 0
723082 376716 0 0
723082 376716 0 0
723082 376716 0 0
723082 376716 0 0
723082 376716 0 0
723082 376716 0 0
7...

output:

100.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000...

result:

ok 495 numbers

Test #10:

score: -100
Wrong Answer
time: 3ms
memory: 4076kb

input:

493 261998
815225 6 0 0
806366 7 0 0
103518 4 0 0
229937 5 0 0
530734 7 0 0
127508 8 0 0
128550 6 0 0
614581 8 0 0
334911 8 0 0
258776 3 0 0
256449 5 0 0
702679 3 0 0
650973 9 0 0
309392 10 0 0
414347 6 0 0
867328 5 0 0
29525 5 0 0
912594 5 0 0
221324 7 0 0
907323 3 0 0
645853 8 0 0
482215 2 0 0
652...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

wrong answer 3rd numbers differ - expected: '1.1023001', found: '0.0000000', error = '1.0000000'