QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1191 | #754232 | #9554. The Wheel of Fortune | ucup-team4125 | ucup-team896 | Success! | 2024-11-18 10:02:46 | 2024-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'
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#754232 | #9554. The Wheel of Fortune | ucup-team896# | WA | 214ms | 18676kb | C++20 | 2.8kb | 2024-11-16 14:33:26 | 2024-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;
}