QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#50345 | #851. (Almost) Fair Cake-Cutting | SGColin | AC ✓ | 3ms | 3792kb | C++17 | 5.3kb | 2022-09-25 14:12:21 | 2022-09-25 14:12:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int rd() {
int x = 0;
bool f = false;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
typedef double T;
#define let const auto
#define lett const T
#define letp const P
#define lets const S
#define letl const L
#define letc const C
const T eps = 1e-8;
#define z(x) (abs((x)) <= eps)
struct P {
T x, y;
P (T x = 0, T y = 0) : x(x), y(y) {}
P operator + (letp &p) const {return {x + p.x, y + p.y};}
P operator - (letp &p) const {return {x - p.x, y - p.y};}
P operator * (lett &d) const {return {x * d, y * d};}
P operator / (lett &d) const {return {x / d, y / d};}
P operator - () const {return {-x, -y};}
T operator | (letp &p) const {return x * p.x + y * p.y;}
T operator ^ (letp &p) const {return x * p.y - y * p.x;}
int ori(letp &p) const {T t = (*this) ^ p; return (t > eps) - (t < -eps);}
T norm() const {return x * x + y * y;}
} zero;
double abs(letp &p) {return sqrt(p.norm());}
P perp(letp &p) {return {-p.y, p.x};}
struct argcmp {
bool operator() (letp &a, letp &b) const {
const auto quad = [](letp &a) {
if (a.y < -eps) return 1;
if (a.y > eps) return 4;
if (a.x < -eps) return 5;
if (a.x > eps) return 3;
return 2;
};
const int qa = quad(a), qb = quad(b);
if (qa != qb) return qa < qb;
const auto t = (a ^ b);
return t > eps;
}
};
struct L {
P p, v;
int ori (letp &a) const {return v.ori(a - p);}
P inter(letl &l) const {return p + v * ((l.v ^ (p - l.p)) / (v ^ l.v));}
double dis(letp &a) const {return abs(v ^ (a - p)) / abs(v);}
};
bool para(letl &p, letl &q) {return z(p.v ^ q.v);}
struct Polygon {
vector<P> p;
Polygon(const vector<P> &p = {}) : p(p) {}
size_t nxt(const size_t i) const {return i == p.size() - 1 ? 0 : i + 1;}
size_t pre(const size_t i) const {return i == 0 ? p.size() - 1 : i - 1;}
T double_area() const {
T sum = 0;
for (size_t i = 0; i < p.size(); ++i) sum += (p[i] ^ p[nxt(i)]);
return abs(sum);
}
double area() const {return double_area() / 2.0;}
};
struct C : Polygon {
C (const vector<P> &p = {}) : Polygon(p) {}
};
vector<L> halfInter(vector<L> l, lett lim = 1e9) {
const auto check = [](letl &a, letl &b, letl &c) {return a.ori(b.inter(c)) < 0;};
const auto cmp = [] (letl &a, letl &b) {
if (abs(a.v ^ b.v) <= eps && (a.v | b.v) >= -eps) return a.ori(b.p) == -1;
return argcmp()(a.v, b.v);
};
l.push_back({{0, 0}, {0, -1}}); l.push_back({{0, 0}, {1, 0}});
l.push_back({{lim, 0}, {0, 1}}); l.push_back({{0, lim}, {-1, 0}});
sort(l.begin(), l.end(), cmp);
deque<L> q;
for (size_t i = 0; i < l.size(); ++i) {
//printf("(%.2lf %.2lf) -> (%.2lf %.2lf)\n", l[i].p.x, l[i].p.y, l[i].v.x, l[i].v.y);
if (i && l[i - 1].v.ori(l[i].v) == 0 && (l[i - 1].v | l[i].v) > eps) continue;
while (q.size() > 1 && check(l[i], q.back(), q[q.size() - 2])) q.pop_back();
while (q.size() > 1 && check(l[i], q[0], q[1])) q.pop_front();
if (!q.empty() && q.back().v.ori(l[i].v) <= 0) return vector<L>();
q.push_back(l[i]);
}
while (q.size() > 1 && check(q[0], q.back(), q[q.size() - 2])) q.pop_back();
while (q.size() > 1 && check(q.back(), q[0], q[1])) q.pop_front();
return vector<L>(q.begin(), q.end());
}
C halfInterConvex(vector<L> l, lett lim = 1e9) {
l = halfInter(l, lim);
vector<P> res; res.resize(l.size());
for (size_t i = 0; i < l.size(); ++i)
res[i] = l[i].inter(l[i == l.size() - 1 ? 0 : i + 1]);
return res;
}
#define N 4007
int a[N], b[N], c[N];
inline void work() {
int n = rd(), m = rd();
for (int i = 1; i <= n; ++i) {
a[i] = rd(); b[i] = rd(); c[i] = rd();
}
if (n >= 3) {puts("100.000000%"); return;}
if (n == 2) {
L l1, l2;
if (a[1] != 0)l1.p = P{-1.0 * c[1] / a[1], 0};
else l1.p = P{0.0, -1.0 * c[1] / b[1]};
l1.v = P{-b[1], a[1]};
if (a[2] != 0)l2.p = P{-1.0 * c[2] / a[2], 0};
else l2.p = P{0.0, -1.0 * c[2] / b[2]};
l2.v = P{-b[2], a[2]};
if (para(l1, l2)) {puts("100.000000%"); return;}
P pos = l1.inter(l2);
if (abs(pos.x) >= m || abs(pos.y) >= m) {puts("100.000000%"); return;}
vector<L> sl(2);
sl[0] = l1; sl[1] = l2;
double mn = 1e18;
mn = min(mn, halfInterConvex(sl, m).area());
//printf("%.10lf\n", mn);
sl[0].v = -sl[0].v;
mn = min(mn, halfInterConvex(sl, m).area());
//printf("%.10lf\n", mn);
sl[1].v = -sl[1].v;
mn = min(mn, halfInterConvex(sl, m).area());
//printf("%.10lf\n", mn);
sl[0].v = -sl[0].v;
mn = min(mn, halfInterConvex(sl, m).area());
//printf("%.10lf\n", mn);
printf("%.6lf", 100 * (1.0 - mn / m / m));
puts("%");
}
if (n == 1) {
vector<L> sl(1);
if (a[1] != 0) sl[0].p = P{-1.0 * c[1] / a[1], 0};
else sl[0].p = P{0.0, -1.0 * c[1] / b[1]};
sl[0].v = P{-b[1], a[1]};
double mn = 1e18;
mn = min(mn, halfInterConvex(sl, m).area());
//printf("%.10lf\n", mn);
sl[0].v = -sl[0].v;
mn = min(mn, halfInterConvex(sl, m).area());
//printf("%.10lf\n", mn);
printf("%.6lf", 100 * (1.0 - mn / m / m));
puts("%");
}
}
int main() {
for (int t = rd(); t; --t) work();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3748kb
input:
1 2 1000 0 1 -750 1 0 -750
output:
93.750000%
result:
ok OK!
Test #2:
score: 0
Accepted
time: 3ms
memory: 3792kb
input:
500 1 1000 1 0 -300 1 1000 1 1 -500 1 1000 1 1 -1000 1 2 0 -1 1 1 1 -1 -1 1 1 1000 -866 287 1 1 1 3 -442 1 1 130 -628 558 0 1 868 -297 166 1 1 479 373 3 -96709 1 68 527 -833 0 1 348 -337 954 -109611 1 917 564 2 -449502 1 16 679 -175 0 1 463 138 -961 3 1 361 -951 -12 45113 1 464 -977 622 -35388 1 351...
output:
70.000000% 87.500000% 50.000000% 50.000000% 50.000000% 83.429446% 99.434389% 55.573248% 72.053484% 53.725926% 68.367347% 50.678631% 86.735384% 87.113402% 92.819305% 87.490351% 75.495542% 99.939269% 79.498817% 99.791156% 100.000000% 99.967926% 71.862629% 87.212627% 99.999999% 52.507599% 95.787352% 98...
result:
ok OK!
Test #3:
score: 0
Accepted
time: 3ms
memory: 3664kb
input:
50 4000 1000 -866 287 1 -246 141 188157 994 0 -948594 3 -442 1 172 -257 2 -77 -628 557282 -983 -297 165987 -172 -992 4695 961 587 -844056 -981 631 897222 289 1 -184824 -463 493 -336717 954 -110 32323 67 866 -240824 893 -111 -546885 259 -818 385562 906 93 -191311 308 -794 258487 502 -855 -273835 -649...
output:
100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% 100.000000% ...
result:
ok OK!