QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#51619 | #985. Attractions On Plane | YaoBIG | WA | 3ms | 4084kb | C++17 | 6.2kb | 2022-10-03 03:29:44 | 2022-10-03 03:29:45 |
Judging History
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 = (a - b).cross(rhs.dir());
if (P::sgn(s1) == 0) return {false, P{}};
return {true, a + (b - a) * 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: 2ms
memory: 3856kb
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: 2ms
memory: 3792kb
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: 0ms
memory: 3856kb
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: 3900kb
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: 3856kb
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: 2ms
memory: 3888kb
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: 2ms
memory: 3732kb
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: 2ms
memory: 3864kb
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: 3ms
memory: 3932kb
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: 0ms
memory: 4084kb
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'