QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#961130 | #8266. Astronomer | Wansur | 0 | 65ms | 4224kb | C++23 | 4.6kb | 2025-04-01 23:30:20 | 2025-04-01 23:30:21 |
Judging History
answer
#include <bits/stdc++.h>
using ll = long long;
// const int N = ;
struct vector2d {
double x, y;
double angle() const {
return atan2(y, x);
}
double dist() const {
return sqrt(x * x + y * y);
}
auto &operator+=(const vector2d &v) {
return x += v.x, y += v.y, *this;
}
auto &operator-=(const vector2d &v) {
return x -= v.x, y -= v.y, *this;
}
friend auto operator-(vector2d a, const vector2d &b) {
return a -= b;
}
friend auto operator+(vector2d a, const vector2d &b) {
return a += b;
}
friend auto operator*(const vector2d &a, double b) {
return vector2d{a.x * b, a.y * b};
}
friend std::ostream &operator<<(std::ostream &os, const vector2d &v) {
return os << "(" << v.x << ", " << v.y << ")";
}
};
struct line {
double x, y;
vector2d v;
};
line perpendicular_bisector(vector2d a, vector2d b) {
return line{(a.x + b.x) / 2, (a.y + b.y) / 2, vector2d{a.y - b.y, b.x - a.x}};
}
auto pi = std::acos(-1.0);
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int k, n;
double s, t;
std::cin >> n >> k;
s = 0, t = 1;
std::vector<vector2d> a(n);
for (auto &[x, y] : a)
std::cin >> x >> y;
std::shuffle(a.begin(), a.end(), std::mt19937());
if (s >= t) {
std::sort(a.begin(), a.end(), [&](auto a, auto b) {
return a.dist() < b.dist();
});
std::cout << std::fixed << std::setprecision(10) << t *a[k - 1].dist() << '\n';
return 0;
}
double ans = 1.5e18;
for (int i = 0; i < n; i++) {
if (k == 1) {
ans = std::min(ans, s * a[i].dist());
continue;
}
auto check = [&](double lim) {
std::vector<std::pair<double, int>> ve;
for (int j = 0; j < n; j++) {
if (i == j)
continue;
auto pb = perpendicular_bisector(a[i], a[j]);
auto calc = [&](auto d) {
auto p = vector2d{pb.x, pb.y} + pb.v *d;
return s * p.dist() + t * (p - a[i]).dist();
};
double l = -1e9, r = 1e9;
for (int t = 100; t; t--) {
double ml = l + (r - l) / 3, mr = r - (r - l) / 3;
if (calc(ml) < calc(mr))
r = mr;
else
l = ml;
}
if (calc(l) > lim)
continue;
double ll = -1e9, lr = l;
for (int t = 100; t; t--) {
double mid = (ll + lr) / 2;
if (calc(mid) < lim)
lr = mid;
else
ll = mid;
}
double rl = l, rr = 1e9;
for (int t = 100; t; t--) {
double mid = (rl + rr) / 2;
if (calc(mid) < lim)
rl = mid;
else
rr = mid;
}
// std::cerr << (vector2d{pb.x, pb.y} + pb.v * ll) << ' ' << calc(ll) << ' ' << (vector2d{pb.x, pb.y} + pb.v * rl) << ' ' << calc(rl) << '\n';
auto al = (vector2d{pb.x, pb.y} + pb.v * ll - a[i]).angle() + pi;
auto ar = (vector2d{pb.x, pb.y} + pb.v * rl - a[i]).angle() + pi;
if (al > ar)
std::swap(al, ar);
if (ar - al > pi)
ve.emplace_back(ar, 1), ve.emplace_back(al + 2 * pi, -1);
else
ve.emplace_back(al, 1), ve.emplace_back(ar, -1), ve.emplace_back(al + 2 * pi, 1), ve.emplace_back(ar + 2 * pi,
-1);
}
std::sort(ve.begin(), ve.end());
int cur = 0;
for (auto [x, y] : ve) {
cur += y;
if (cur >= k - 1)
return 1;
}
return 0;
};
double l = 0, r = ans;
if (!check(r))
continue;
for (int t = 100; t; t--) {
double mid = (l + r) / 2;
if (check(mid))
r = mid;
else
l = mid;
}
ans = std::min(ans, r);
std::cerr << i << '\n';
}
std::cout << std::fixed << std::setprecision(10) << ans * ans * acos(-1) << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 4224kb
input:
5 50 100 10 83800992 -886133390 419292091 -739946592 23316601 -533703422 728805984 890308742 -66894195 66628784 154560403 -595148422 -827958439 928301296 849961738 946067907 310878751 -114000318 871656204 66733904 -791356839 125420374 -838471381 157736324 -911519472 -679917398 816843257 -363318953 -...
output:
7068583470577033914006087004170747904.0000000000
result:
wrong answer 1st numbers differ - expected: '4930145422.6525173', found: '7068583470577033914006087004170747904.0000000', error = '1433747458665021241458425856.0000000'
Subtask #2:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 65ms
memory: 4096kb
input:
50 50 0 100 -636373727 151906670 -436420422 -967929931 -946894101 -648810265 -318412226 -368156635 608567780 -787997497 40618170 966479708 -451370311 -406325088 830840722 -678655131 -89071166 -21371001 60891837 -615893965 785687617 -623669416 -513873386 -653229486 -555272924 350850129 -901712781 -32...
output:
5194980760581571584.0000000000
result:
wrong answer 1st numbers differ - expected: '128592913281.7085724', found: '5194980760581571584.0000000', error = '40398654.1669525'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Wrong Answer
Test #214:
score: 0
Wrong Answer
time: 0ms
memory: 4224kb
input:
5 50 100 10 460309761 -799742665 -100987677 761175444 -361900447 -449675625 -631196407 -1559607 -721861391 643436364 -122962913 5884730 295248578 491223378 986298998 468191512 -169039995 374919122 -46710929 402201182 -943494268 -547915393 521170382 929707215 355890998 688700401 -264192618 -469266213...
output:
7068583470577033914006087004170747904.0000000000
result:
wrong answer 1st numbers differ - expected: '3882365967.1217990', found: '7068583470577033914006087004170747904.0000000', error = '1820689633702240855202463744.0000000'
Subtask #7:
score: 0
Skipped
Dependency #1:
0%