QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#280630#7783. Military Maneuverucup-team1198#WA 804ms4044kbC++149.2kb2023-12-09 17:20:082023-12-09 17:20:08

Judging History

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

  • [2023-12-09 17:20:08]
  • 评测
  • 测评结果:WA
  • 用时:804ms
  • 内存:4044kb
  • [2023-12-09 17:20:08]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

struct Point {
  long double x, y;
  Point(long double x, long double y): x(x), y(y) {}
  Point(): x(0ll), y(0ll) {}
};

Point operator+(const Point& first, const Point& second) {
  return Point(first.x + second.x, first.y + second.y);
}

Point operator-(const Point& first, const Point& second) {
  return Point(first.x - second.x, first.y - second.y);
}

long double cross(const Point& first, const Point& second) {
  return first.x * second.y - first.y * second.x;
}

long double dot(const Point& first, const Point& second) {
  return first.x * second.x + first.y * second.y;
}

long double sqrlen(const Point& P) {
  return P.x * P.x + P.y * P.y;
}

long double len(const Point& P) {
  return sqrtl(sqrlen(P));
}

const long double INF = 1e9;
const long double EPS = 1e-7;

struct Line{
  long double a;
  long double b;
  long double c;
  Line(long double a, long double b, long double c): a(a), b(b), c(c) {}
  Point get_perp() const {
    return Point(a, b);
  }
  long double get_y_by_x(long double x) const {
    return (-c - a * x) / b;
  }
};

long double inter(const Line& l1, const Line& l2) {
  return (-l1.c * l2.b + l2.c * l1.b) / (l1.a * l2.b - l2.a * l1.b);
}

// ax + by+c>=0

vector<Point> halfplane_inter(vector<Line>& lines) {
  long double min_x = -INF;
  long double max_x = INF;
  vector<Line> up;
  vector<Line> down;
  for (Line l : lines) {
    if (l.b == 0) {
      if (l.a > 0) {
        min_x = max(min_x, -l.c / l.a);
      } else {
        max_x = min(max_x, -l.c / l.a);
      }
    } else if (l.b > 0) {
      up.emplace_back(l);
    } else {
      down.emplace_back(l);
    }
  }

  if (max_x - min_x < EPS) {
    return {};
  }
  sort(up.begin(), up.end(), [](const Line& l1, const Line& l2) {
    if (abs(cross(l1.get_perp(), l2.get_perp())) < EPS) {
      // parallel
      return l1.c / len(l1.get_perp()) < l2.c / len(l2.get_perp());
    }
    return cross(l1.get_perp(), l2.get_perp()) > 0;
  });
  vector<Line> up_hull;
  vector<long double> up_xs;
  for (Line l : up) {
    // skip parallel
    if (!up_hull.empty() && abs(cross(up_hull.back().get_perp(), l.get_perp())) < EPS)
      continue;
    if (up_hull.empty()) {
      up_hull.emplace_back(l);
      continue;
    }
    while (!up_xs.empty() && EPS >= inter(up_hull.back(), l) - up_xs.back()) {
      up_hull.pop_back();
      up_xs.pop_back();
    }
    up_xs.emplace_back(inter(up_hull.back(), l));
    up_hull.emplace_back(l);
  }

  sort(down.begin(), down.end(), [](const Line& l1, const Line& l2) {
    if (abs(cross(l1.get_perp(), l2.get_perp())) < EPS) {
      // parallel
      return l1.c / len(l1.get_perp()) < l2.c / len(l2.get_perp());
    }
    return cross(l1.get_perp(), l2.get_perp()) < 0;
  });
  vector<Line> down_hull;
  vector<long double> down_xs;
  for (Line l : down) {
    // skip parallel
    if (!down_hull.empty() && abs(cross(down_hull.back().get_perp(), l.get_perp())) < EPS)
      continue;
    if (down_hull.empty()) {
      down_hull.emplace_back(l);
      continue;
    }
    while (!down_xs.empty() && EPS >= inter(down_hull.back(), l) - down_xs.back()) {
      down_hull.pop_back();
      down_xs.pop_back();
    }
    down_xs.emplace_back(inter(down_hull.back(), l));
    down_hull.emplace_back(l);
  }

  int i1 = 0;
  int i2 = 0;
  while (i1 < up_xs.size() && up_xs[i1] < min_x)
    ++i1;
  while (i2 < down_xs.size() && down_xs[i2] < min_x)
    ++i2;
  long double prev = min_x;
  vector<Point> points;
  auto try_pushing_points = [&](long double x, int i1, int i2) {
    long double y_up = up_hull[i1].get_y_by_x(x);
    long double y_down = down_hull[i2].get_y_by_x(x);
    if (y_down - y_up > EPS) {
      points.emplace_back(x, y_up);
      points.emplace_back(x, y_down);
    }
    if (abs(cross(up_hull[i1].get_perp(), down_hull[i2].get_perp())) > EPS) {
      long double cur_x = inter(up_hull[i1], down_hull[i2]);
      if (prev <= cur_x && cur_x <= x)
        points.emplace_back(cur_x, up_hull[i1].get_y_by_x(cur_x));
    }
    prev = x;
  };
  try_pushing_points(min_x, i1, i2);
  while (i1 < up_xs.size() || i2 < down_xs.size()) {
    long double cur_x = 0;
    int old_i1 = i1;
    int old_i2 = i2;
    if (i1 < up_xs.size() && (i2 == down_xs.size() || up_xs[i1] < down_xs[i2])) {
      cur_x = up_xs[i1];
      ++i1;
    } else {
      cur_x = down_xs[i2];
      ++i2;
    }
    if (cur_x > max_x)
      cur_x = max_x;
    try_pushing_points(cur_x, old_i1, old_i2);
    if (cur_x == max_x)
      break;
  }
  if (prev < max_x) {
    try_pushing_points(max_x, i1, i2);
  }
  return points;
}

void srt(vector<Point>& arr) {
  Point p0 = arr[0];
  sort(arr.begin(), arr.end(), [&p0](Point a, Point b) {
    if (cross(a - p0, b - p0) == 0) {
      return sqrlen(a - p0) < sqrlen(b - p0);
    } 
    return cross(a - p0, b - p0) < 0;
  });
}

long double get(const vector<Point>& arr, int alpha) {
  int k = arr.size();
  long double ans = 0;
  long double minx = 1e9, maxx = -1e9;
  for (int i = 0; i < k; ++i) {
    minx = min(minx, arr[i].x);
    maxx = max(maxx, arr[i].x);
  }
  for (int i = 0; i < k; ++i) {
    long double x1 = arr[i].x;
    long double x2 = arr[(i + 1) % k].x;
    long double y1 = arr[i].y;
    long double y2 = arr[(i + 1) % k].y;
    if (abs(x2 - x1) < 1e-12 && (abs(x1 - minx) < 1e-12 || abs(x1 - maxx) < 1e-12)) continue;
    long double dlta = 1;
    long double add = x1;
    for (int i = 1; i <= alpha; ++i) {
      dlta = dlta * x2 + add;
      add *= x1;
    }
    long double dlta2 = dlta * x2 + add;
    ans += dlta / (alpha + 1) * (y1 * x2 - x1 * y2) + dlta2 / (alpha + 2) * (y2 - y1);
  }
  return ans;
} 

int main() {
#ifdef DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
#endif

  int xl, yl, xr, yr;
  cin >> xl >> yl >> xr >> yr;
  int n;
  cin >> n;
  vector<array<int, 2>> arr(n);
  for (int i = 0; i < n; ++i) {
    cin >> arr[i][0] >> arr[i][1];
  }
  long double ans = 0;
  for (int i = 0; i < n; ++i) {
      vector<Line> hp;
      hp.push_back({1, 0, -xl});
      hp.push_back({-1, 0, xr});
      hp.push_back({0, 1, -yl});
      hp.push_back({0, -1, yr});
      for (int j = 0; j < n; ++j) {
        if (i == j) continue;
        long double A = arr[j][0] - arr[i][0];
        long double B = arr[j][1] - arr[i][1];
        long double x = arr[i][0] + arr[j][0];
        long double y = arr[i][1] + arr[j][1];
        x /= 2;
        y /= 2;
        long double C = -A * x - B * y;
        /// cerr << i << ": " << A << " " << B << " " << C << endl;
        /// cerr << A * arr[j][0] + B * arr[j][1] + C << endl;
        hp.push_back({A, B, C});
      }
      auto res = halfplane_inter(hp);
      if (!res.empty()) {
        srt(res);
        /**cerr << "res: " << endl;
        for (auto elem : res) {
          cerr << elem.x << " " << elem.y << endl;
        }*/
        long double I2 = get(res, 2);
        long double I1 = get(res, 1);
        long double I0 = get(res, 0);
        /// cerr << i << ": " << I0 << " " << I1 << " " << I2 << endl;
        ans += I2 - 2 * I1 * arr[i][0] + I0 * arr[i][0] * arr[i][0];
        for (Point& p : res) {
          swap(p.x, p.y);
        }
        reverse(res.begin(), res.end());
        I2 = get(res, 2);
        I1 = get(res, 1);
        I0 = get(res, 0);
        /// cerr << i << ": " << I0 << " " << I1 << " " << I2 << endl;
        ans += I2 - 2 * I1 * arr[i][1] + I0 * arr[i][1] * arr[i][1];
      }

      hp.clear();
      hp.push_back({1, 0, -xl});
      hp.push_back({-1, 0, xr});
      hp.push_back({0, 1, -yl});
      hp.push_back({0, -1, yr});
      for (int j = 0; j < n; ++j) {
        if (i == j) continue;
        long double A = arr[j][0] - arr[i][0];
        long double B = arr[j][1] - arr[i][1];
        long double x = arr[i][0] + arr[j][0];
        long double y = arr[i][1] + arr[j][1];
        x /= 2;
        y /= 2;
        long double C = -A * x - B * y;
        hp.push_back({-A, -B, -C});
      }
      res = halfplane_inter(hp);
      if (!res.empty()) {
        srt(res);
        /**cerr << "res: " << endl;
        for (auto elem : res) {
          cerr << elem.x << " " << elem.y << endl;
        }*/
        long double I2 = get(res, 2);
        long double I1 = get(res, 1);
        long double I0 = get(res, 0);
        ans -= I2 - 2 * I1 * arr[i][0] + I0 * arr[i][0] * arr[i][0];
        for (Point& p : res) {
          swap(p.x, p.y);
        }
        reverse(res.begin(), res.end());
        I2 = get(res, 2);
        I1 = get(res, 1);
        I0 = get(res, 0);
        ans -= I2 - 2 * I1 * arr[i][1] + I0 * arr[i][1] * arr[i][1];
      }
  }
  ans /= (xr - xl) * (yr - yl);
  long double PI = 3.141592653589793238;
  cout << fixed << setprecision(20);
  cout << PI * ans << "\n";
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3844kb

input:

0 0 2 2
2
3 1
1 3

output:

8.37758040957278164382

result:

ok found '8.3775804', expected '8.3775804', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

0 0 2 2
2
5 1
1 3

output:

37.69911184307751739198

result:

ok found '37.6991118', expected '37.6991118', error '0.0000000'

Test #3:

score: -100
Wrong Answer
time: 804ms
memory: 4044kb

input:

-2911 2151 336 5941
2000
-83 79
-94 47
48 -29
-47 64
84 75
-44 -86
-58 -11
-31 58
20 53
80 -19
-82 74
-60 -26
8 -68
-42 -61
-14 12
-58 -18
92 10
35 -26
71 64
76 89
-80 6
70 4
-96 -99
95 -80
-3 -22
71 -89
-75 17
-35 -82
-59 95
60 48
-74 50
-82 90
-26 5
-75 -31
-45 85
85 14
-70 -57
59 46
55 13
-23 60
...

output:

4980913.46837657743753879913

result:

wrong answer 1st numbers differ - expected: '6657168.1428534', found: '4980913.4683766', error = '0.2517970'