QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#136464#3410. Jiajia's RobotLiceWA 2ms4292kbC++203.7kb2023-08-08 20:18:282023-08-08 20:18:31

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-08 20:18:31]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4292kb
  • [2023-08-08 20:18:28]
  • 提交

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;
}

详细

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'