QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#136464 | #3410. Jiajia's Robot | Lice | WA | 2ms | 4292kb | C++20 | 3.7kb | 2023-08-08 20:18:28 | 2023-08-08 20:18:31 |
Judging History
answer
#include <bits/stdc++.h>
const double EPS = 1e-8;
const double PI = acos(-1);
#define sqr(x) ((x) * (x))
#define equals(x, y) (fabs((x) - (y)) < EPS)
#define all(x) (x).begin(), (x).end()
const int N = 5;
int n;
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) { }
bool operator == (const Point &rhs) const { return equals(x, rhs.x) && equals(y, rhs.y); }
};
using polygon = std::vector<Point>;
Point operator + (const Point& a, const Point& b) {
return Point(a.x + b.x, a.y + b.y);
}
Point operator - (const Point& a, const Point& b) {
return Point(a.x - b.x, a.y - b.y);
}
double dot(const Point& a, const Point& b) {
return a.x * b.x + a.y * b.y;
}
double cross(const Point& a, const Point& b) {
return a.x * b.y - a.y * b.x;
}
double dist(const Point& a, const Point& b) {
return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}
Point polar(double a, double r) {
return Point(r * cos(a), r * sin(a));
}
double arg(Point x) {
return atan2(x.y, x.x);
}
struct Circle {
Point o;
double r;
bool operator == (const Circle& rhs) const {
return equals(o.x, rhs.o.x) && equals(o.y, rhs.o.y) && equals(r, rhs.r);
}
Circle() { }
Circle(Point a, Point b) {
o = a + b;
o.x /= 2, o.y /= 2;
r = dist(a, b) / 2;
}
} c[N];
bool include(Circle a, Circle b) {
return a.r + EPS > b.r + dist(a.o, b.o);
}
bool insection(Circle a, Circle b) {
return !include(a, b) && !include(b, a) && a.r + b.r > dist(a.o, b.o) + EPS;
}
double adj(double a) {
if (a > PI * 2 - EPS) a -= PI * 2;
if (a < 0) a += PI * 2;
return a;
}
std::pair<double, double> crossPoints(Circle a, Circle b) {
double d = dist(a.o, b.o);
double alpha = acos((sqr(d) + sqr(a.r) - sqr(b.r)) / (2 * a.r * d));
double beta = adj(arg(b.o - a.o));
return {adj(beta - alpha), adj(beta + alpha)};
}
int cnt[N];
double ans[N];
polygon g[N];
double solve() {
for (int i = 1; i <= n; i++) {
cnt[i] = ans[i] = 0;
g[i].clear();
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) if (i != j)
if (include(c[i], c[j])) ++cnt[j];
for (int i = 1; i <= n; i++) {
std::vector<std::pair<double, int>> vec;
int cur = cnt[i];
for (int j = 1; j <= n; j++) if (i != j) {
if (!insection(c[i], c[j])) continue;
auto [u, v] = crossPoints(c[i], c[j]);
if (u > v) ++cur;
vec.emplace_back(u, 1);
vec.emplace_back(v, -1);
}
if (vec.empty()) {
ans[cnt[i] + 1] += sqr(c[i].r) * PI;
continue;
}
std::sort(all(vec));
for (int j = 0; j < (int)vec.size(); j++) {
double a = vec[j].first, b = vec[(j + 1) % vec.size()].first;
cur += vec[j].second;
double t = adj(b - a);
ans[cur + 1] += 0.5 * sqr(c[i].r) * (t - sin(t));
g[cur + 1].push_back(polar(a, c[i].r) + c[i].o);
g[cur + 1].push_back(polar(b, c[i].r) + c[i].o);
}
}
for (int i = 1; i <= n; i++)
for (int j = 0; j < (int)g[i].size(); j += 2)
ans[i] += cross(g[i][j], g[i][(j + 1) % g[i].size()]) / 2;
for (int i = 1; i < n; i++)
ans[i] -= ans[i + 1];
return ans[1] + ans[2] + ans[3];
}
int main() {
for (int t = 1; ; t++) {
Point a, b, c, d;
scanf("%lf%lf", &a.x, &a.y);
scanf("%lf%lf", &b.x, &b.y);
scanf("%lf%lf", &c.x, &c.y);
scanf("%lf%lf", &d.x, &d.y);
if (a == Point(0, 0) && b == Point(0, 0) && c == Point(0, 0) && d == Point(0, 0))
break;
n = 4;
::c[1] = Circle(a, c);
::c[2] = Circle(a, d);
::c[3] = Circle(b, c);
::c[4] = Circle(b, d);
printf("Case %d: %.3f\n\n", t, solve());
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 4292kb
input:
1 1 2 1 1 2 2 2 1 1 100 1 1 2 100 2 1 1 2 1 1 100 2 100 350 95 496 113 481 159 117 434 218 301 337 385 314 131 302 255 367 328 37 51 272 402 68 68 55 150 261 239 78 488 78 404 72 264 82 273 196 179 40 151 158 6 157 426 341 476 158 403 117 262 87 468 289 120 245 86 152 10 443 385 420 456 131 345 407 ...
output:
Case 1: 1.285 Case 2: 50.285 Case 3: 148.498 Case 4: 202859.189 Case 5: 55995.849 Case 6: 165932.981 Case 7: 97504.975 Case 8: 22754.487 Case 9: 220205.617 Case 10: 112014.542 Case 11: 234072.564 Case 12: 101060.994 Case 13: 60348.415 Case 14: 93181.588 Case 15: 144300.615 Case 16: 17...
result:
wrong answer 1st lines differ - expected: 'Case 1: 2.071', found: 'Case 1: 1.285'