QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#551684 | #9253. Prism Palace | ucup-team3584# | WA | 1ms | 4060kb | C++20 | 3.6kb | 2024-09-07 17:46:19 | 2024-09-07 17:46:20 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<ll> x(n), y(n);
for (int i = 0; i < n; ++i) {
cin >> x[i] >> y[i];
}
x.push_back(x[0]), y.push_back(y[0]);
vector<pair<ll, ll>> v(n);
for (int i = 0; i < n; ++i) {
v[i].first = x[i + 1] - x[i];
v[i].second = y[i + 1] - y[i];
}
map<pair<ll, ll>, vector<int>> mp;
for (int i = 0; i < n; i++) {
if (v[i].first == 0) {
mp[{1, 0}].push_back(i);
} else if (v[i].second == 0) {
mp[{0, 1}].push_back(i);
} else {
if (v[i].first < 0) {
v[i].first = -v[i].first, v[i].second = -v[i].second;
}
ll a = v[i].first, b = v[i].second;
ll g = gcd(a, abs(b));
a /= g, b /= g;
mp[{a, -b}].push_back(i);
}
}
double res = 0;
vector<pair<ll, ll>> ang;
ang.emplace_back(0, 1);
ang.emplace_back(1, 0);
for (const auto &p : mp) {
ang.push_back(p.first);
}
sort(ang.begin(), ang.end());
ang.erase(unique(ang.begin(), ang.end()), ang.end());
sort(ang.begin(), ang.end(), [&](auto p, auto q) {
if (p.first == 0) return true;
if (q.first == 0) return false;
return p.second * q.first > p.first * q.second;
});
vector<bool> minus(n);
multiset<pair<ll, ll>> st;
ll xs = 0, ys = 0;
for (int i = 0; i < n; ++i) {
if (v[i].second >= 0) {
minus[i] = false;
st.insert({v[i].first, v[i].second});
xs += v[i].first, ys += v[i].second;
} else {
minus[i] = true;
st.insert({-v[i].first, -v[i].second});
xs -= v[i].first, ys -= v[i].second;
}
}
auto calc = [&](ll px, ll py, ll nx, ll ny) -> void {
ll uo = px * px + py * py + nx * nx + ny * ny - (px - nx) * (px - nx) - (py - ny) * (py - ny);
ll ui = 4LL * (px * px + py * py) * (nx * nx + ny * ny);
long double cs = uo / sqrt((long double)ui);
long double p = acos(cs) / acos((long double)-1.0) / 2;
res += p;
};
auto update = [&](int j) {
ll a = v[j].first, b = v[j].second;
if (minus[j]) a = -a, b = -b, minus[j] = false;
else minus[j] = true;
auto it = st.find({a, b});
st.erase({a, b});
st.insert({-a, -b});
xs -= 2LL * a, ys -= 2LL * b;
};
ll px = 0, py = 1;
for (int i = 1; i < ang.size(); ++i) {
ll nx = ang[i].first, ny = ang[i].second;
if (xs % 2 == 0 and ys % 2 == 0 and st.find({xs / 2, ys / 2}) != st.end()) {
calc(px, py, nx, ny);
}
for (auto j : mp[ang[i]]) {
update(j);
}
px = nx, py = ny;
}
for (int i = 0; i < ang.size(); ++i) {
ll nx = -ang[i].first, ny = -ang[i].second;
if (xs % 2 == 0 and ys % 2 == 0 and st.find({xs / 2, ys / 2}) != st.end()) {
calc(px, py, nx, ny);
}
for (auto j : mp[ang[i]]) {
update(j);
}
px = nx, py = ny;
}
{
ll nx = ang[0].first, ny = ang[0].second;
if (xs % 2 == 0 and ys % 2 == 0 and st.find({xs / 2, ys / 2}) != st.end()) {
calc(px, py, nx, ny);
}
}
printf("%.12f\n", res);
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4060kb
input:
3 0 0 1 0 0 1
output:
1.000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 4048kb
input:
4 0 0 0 1 1 1 1 0
output:
1.000000000000
result:
wrong answer 1st numbers differ - expected: '0.0000000', found: '1.0000000', error = '1.0000000'