QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#121773 | #851. (Almost) Fair Cake-Cutting | karuna# | AC ✓ | 3ms | 3780kb | C++17 | 5.0kb | 2023-07-08 20:28:57 | 2023-07-08 20:28:59 |
Judging History
answer
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
struct point {
double x, y;
};
point operator-(point a, point b) {
return {a.x - b.x, a.y - b.y};
}
double operator/(point a, point b) {
return a.x * b.y - a.y * b.x;
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
vector<array<int, 3>> p(n);
for (auto &[x, y, z] : p) cin >> x >> y >> z;
if (n >= 3) {
cout << "100.000000%\n";
continue;
}
else {
vector<pair<point, int>> pt;
pt.push_back({point{0, 0}, 0});
pt.push_back({point{(double)m, 0}, 0});
pt.push_back({point{(double)m, (double)m}, 0});
pt.push_back({point{0, (double)m}, 0});
bool flag = false;
for (int i = 0; i < p.size(); i++) {
auto [a, b, c] = p[i];
double x;
double y;
int cnt = 0;
if (b != 0) {
x = 0; y = -c / (double)b;
if (0 <= y && y <= m) pt.push_back({point{x, y}, i + 1}), ++cnt;
x = m; y = (-c - a * m) / (double)b;
if (0 <= y && y <= m) pt.push_back({point{x, y}, i + 1}), ++cnt;
}
if (a != 0) {
y = 0; x = -c / (double)a;
if (0 < x && x < m) pt.push_back({point{x, y}, i + 1}), ++cnt;
y = m; x = (-c - b * m) / (double)a;
if (0 < x && x < m) pt.push_back({point{x, y}, i + 1}), ++cnt;
}
if (cnt != 2) {
flag = true;
cout << "100.000000%\n";
break;
}
}
if (flag) continue;
auto f = [&](double x, double y) {
if (y == 0) return x;
else if (x == m) return m + y;
else if (y == m) return 3 * m - x;
else return 4 * m - y;
};
if (n == 2) {
auto [a1, b1, c1] = p[0];
auto [a2, b2, c2] = p[1];
if (a1 * b2 - a2 * b1 == 0) {
cout << "100.000000%\n";
continue;
}
double x = (c2 * b1 - c1 * b2) / (double)(a1 * b2 - b1 * a2);
double y = (c2 * a1 - c1 * a2) / (double)(b1 * a2 - a1 * b2);
if (!(0 < x && x < m && 0 < y && y < m)) {
cout << "100.000000%\n";
continue;
}
sort(pt.begin(), pt.end(), [&](auto p, auto q) {
return f(p.first.x, p.first.y) < f(q.first.x, q.first.y);
});
point origin = {x, y};
// for (int i = 0; i < 8; i++) {
// auto [x, y] = pt[i].first;
// cout << x << ' '<< y << endl;
// }
// cout << origin.x << ' ' << origin.y << '\n';
double ans = 1e9;
for (int i = 0; i < 8; i++) {
if (pt[i].second == 0) continue;
double area = 0;
for (int j = 0; j < 8; j++) {
point s = pt[(i + j) % 8].first;
point t = pt[(i + j + 1) % 8].first;
area += (s - origin) / (t - origin) * 0.5;
if (pt[(i + j + 1) % 8].second != 0) break;
}
ans = min(ans, area);
}
ans = (double)m * m - ans;
ans /= (double)m * m;
ans = ans * 100;
cout.precision(6);
cout << fixed << ans << "%\n";
}
else {
sort(pt.begin(), pt.end(), [&](auto p, auto q) {
return f(p.first.x, p.first.y) < f(q.first.x, q.first.y);
});
double ans = 1e9;
for (int i = 0; i < 6; i++) {
if (pt[i].second == 0) continue;
point origin = pt[i].first;
double area = 0;
for (int j = 1; j < 6; j++) {
point s = pt[(i + j) % 6].first;
point t = pt[(i + j + 1) % 6].first;
area += (s - origin) / (t - origin) * 0.5;
if (pt[(i + j + 1) % 6].second != 0) break;
}
ans = min(ans, area);
}
ans = (double)m * m -ans;
ans /= (double)m * m;
ans = ans * 100;
cout.precision(6);
cout << fixed << ans << "%\n";
}
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3744kb
input:
1 2 1000 0 1 -750 1 0 -750
output:
93.750000%
result:
ok OK!
Test #2:
score: 0
Accepted
time: 1ms
memory: 3780kb
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: 3464kb
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!