QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1191#754232#9554. The Wheel of Fortuneucup-team4125ucup-team896Success!2024-11-18 10:02:462024-11-18 10:02:46

Details

Extra Test:

Wrong Answer
time: 0ms
memory: 6260kb

input:

4 31
1 2
1 3
-4 1
-2 -1
-1 2

output:

0.032380486
0.000000000
0.432940843
0.181737495

result:

wrong answer 1st numbers differ - expected: '0.0809512', found: '0.0323805', error = '0.0485707'

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#754232#9554. The Wheel of Fortuneucup-team896#WA 214ms18676kbC++202.8kb2024-11-16 14:33:262024-11-18 10:03:32

answer

#include <bits/stdc++.h>
using namespace std;
typedef long double ldb;
#define double ldb
constexpr int MAXN = 100005;
constexpr double PI = numbers::pi_v<double>;
int n, m, X[MAXN], Y[MAXN], Ox, Oy;
int64_t S, GxS, GyS; double Ax, Ay, Sum[MAXN], Ans[MAXN];
template <class U, class V = U> V cross(U x1, U y1, U x2, U y2){return (V)x1 * y2 - (V)x2 * y1;}
struct Point{
  double x, y, alpha;
  Point(int x_, int y_): x(x_ - Ax), y(y_ - Ay), alpha(atan2(y, x)){}
  Point(double x): x(0), y(0), alpha(x){}
  bool operator < (const Point &o) const {
    if(alpha != o.alpha) return alpha < o.alpha;
    return x < o.x || (x == o.x && y < o.y);
  }
  bool operator == (const Point &o) const {return x == o.x && y == o.y;}
};
double calc(const vector<Point> &P, double alpha){
  size_t r = (lower_bound(P.begin(), P.end(), alpha) - P.begin()) % P.size(), l = (r + P.size() - 1) % P.size();
  double dr = hypot(P[r].x, P[r].y), dl = hypot(P[l].x, P[l].y);
  double beta = P[r].alpha - alpha, gamma = alpha - P[l].alpha;
  double s = cross(P[l].x, P[l].y, P[r].x, P[r].y);
  return Sum[l] - s * dr * sin(beta) / (dr * sin(beta) + dl * sin(gamma));
}
void solve(const vector<Point> &P, int k){
  if(P.empty()) return;
  Sum[0] = 0;
  for(size_t i = 0; i < P.size(); i++){
    int j = (i + 1) % P.size();
    Sum[i + 1] = Sum[i] += cross(P[i].x, P[i].y, P[j].x, P[j].y);
  }
  for(int i = 0; i < n; i++){
    int j = (i + 1) % n;
    double p = calc(P, atan2<double>(Y[i] - Oy, X[i] - Ox)), q = calc(P, atan2<double>(Y[j] - Oy, X[j] - Ox));
    Ans[i] += (q - p + (p > q) * Sum[P.size()]) * k;
  }
}
int main(){
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for(int i = 0; i < n; i++) cin >> X[i] >> Y[i];
  cin >> Ox >> Oy;
  for(int i = 0; i < n; i++){
    int j = (i + 1) % n; int64_t s = cross<int, int64_t>(X[i], Y[i], X[j], Y[j]);
    S += s, GxS += int64_t(X[i] + X[j]) * s, GyS += int64_t(Y[i] + Y[j]) * s;
  } assert(S > 0);
  Ax = double(Ox * (S + m * 2) - (double)GxS / 3) / (m * 2) - 1.1451423e-15;
  Ay = double(Oy * (S + m * 2) - (double)GyS / 3) / (m * 2) + 1.9260817e-15;
  vector<Point> P, Q;
  for(int i = 0; i < n; i++){
    int j = (i + 1) % n; double s = cross<double>(X[j] - X[i], Y[j] - Y[i], Ax - X[i], Ay - Y[i]);
    if(s > 0) P.emplace_back(X[i], Y[i]), P.emplace_back(X[j], Y[j]);
    else      Q.emplace_back(X[i], Y[i]), Q.emplace_back(X[j], Y[j]);
  }
  if(!Q.empty()){
    P.emplace_back(2 * Ax - Ox, 2 * Ay - Oy);
    Q.emplace_back(2 * Ax - Ox, 2 * Ay - Oy);
  }
  sort(P.begin(), P.end()), P.erase(unique(P.begin(), P.end()), P.end()), solve(P,  1);
  sort(Q.begin(), Q.end()), Q.erase(unique(Q.begin(), Q.end()), Q.end()), solve(Q, -1);
  cout << fixed << setprecision(9);
  for(int i = 0; i < n; i++) assert(!isnan(Ans[i])), cout << abs(Ans[i]) / S << '\n';
  return 0;
}