QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#961127 | #8266. Astronomer | Wansur | 0 | 7ms | 3968kb | C++23 | 6.4kb | 2025-04-01 23:26:24 | 2025-04-01 23:26:24 |
Judging History
answer
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define com complex<ld>
#define ld long double
#define ii pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vc vector<char>
#define vs vector<string>
#define vd vector<ld>
#define vcom vector<com>
#define vld vector<ld>
#define vvld vector<vld>
#define vll vector<ll>
#define vvi vector<vi>
#define vvii vector<vii>
#define vvc vector<vc>
#define vvs vector<vs>
#define vvll vector<vll>
#define vvd vector<vd>
#define vvcom vector<vcom>
#define vvld vector<vld>
#define FOR(x,n) for(int x=0;x<(n);x++)
#define FORS(x,n) for(int x=1;x<=(n);x++)
#define FORE(x,a) for(auto &x: a)
#define FORT(x,a,b) for(int x=(a);x<(b);x++)
#define FORD(x,a,b) for(int x=(a);x>=(b);x--)
#define ALL(x) x.begin(),x.end()
#define REP(n) for(int _ = 0; _ < n; _++)
#define MT make_tuple
#define MP make_pair
#define pb push_back
#define F first
#define S second
#define vvvll vector<vvll>
#define sz(x) ((int)x.size())
#ifndef M_PI
#define M_PI (acosl(-1))
#endif
ld err(ld a, ld b)
{
ld d = abs(b - a);
ld m = max((ld)(1), max(abs(a),abs(b)));
return d / m;
}
// kactl geometry
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x = 0, T y = 0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }
bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
P operator+(P p) const { return P(x + p.x, y + p.y); }
P operator-(P p) const { return P(x - p.x, y - p.y); }
P operator*(T d) const { return P(x * d, y * d); }
P operator/(T d) const { return P(x / d, y / d); }
T dot(P p) const { return x * p.x + y * p.y; }
T cross(P p) const { return x * p.y - y * p.x; }
T cross(P a, P b) const { return (a - *this).cross(b - *this); }
T dist2() const { return x * x + y * y; }
ld dist() const { return sqrt((ld)dist2()); }
// angle to x-axis in interval [-pi, pi]
ld angle() const { return atan2(y, x); }
P unit() const { return *this / dist(); } // makes dist()=1
P perp() const { return P(-y, x); }
P normal() const { return perp().unit(); }
P rotate(ld a) const {
return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
}
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")";
}
};
typedef Point<ld> Pd;
vector<Pd> ps;
ll k, n;
ld s,t;
vvld cmp;
vvld cb;
bool sweep(int u, ld cst, ld eps) {
if(s*ps[u].dist() > cst) return false;
vector<pair<ld,int>> e; // Events (Angle,change) where change is whether a new point was added or removed.
FOR(v,n) {
if(u == v) continue;
if(cb[u][v] > cst) continue;
Pd mp = (ps[u]+ps[v])/2;
Pd dir = (ps[v]-ps[u]).perp().unit();
ld lmi = -1e9, lma = cmp[u][v];
ld rmi = cmp[u][v], rma = 1e9;
while(err(lmi,lma) > eps) {
ld md = (lmi + lma)/2;
ld c = (mp + dir*md).dist()*s + (mp + dir*md - ps[u]).dist()*t;
if(c < cst) {
lma = md;
} else {
lmi = md;
}
}
while(err(rmi,rma) > eps) {
ld md = (rmi + rma)/2;
ld c = (mp + dir*md).dist()*s + (mp + dir*md - ps[u]).dist()*t;
if(c < cst) {
rmi = md;
} else {
rma = md;
}
}
//cout << rmi << " " << rma << " " << cmp[u][v] << endl;
ld langle = (mp + dir*(lmi+lma)/2-ps[u]).angle();
ld rangle = (mp + dir*(rmi+rma)/2-ps[u]).angle();
//cout << " " << cst << " " << v << " " << langle << " " << rangle << endl;
e.pb({langle,1});
e.pb({rangle,-1});
if(langle > rangle) { // Crosses starting point
e.pb({-M_PI,1});
e.pb({M_PI,-1});
}
}
sort(ALL(e));
int cr = 1;
if(cr >= k) return true;
//cout << e.size() << endl;
FORE(v,e) {
cr += v.S;
if(cr >= k) {
//cout << ps[u] << " " << cst << endl;
return true;
}
}
return false;
}
int main() {
ll os, ot;
cin >> n >> k;
os = 0, ot = 1;
s = os;
t = ot;
s /= t;
t = 1;
FOR(i, n) {
int x, y;
cin >> x >> y;
ps.pb(Pd(x, y));
}
cb.resize(n,vld(n));
cmp.resize(n,vld(n));
cout << setprecision(12) << fixed;
if (t <= s) {
vd d(n);
FOR(i, n) d[i] = ps[i].dist();
sort(ALL(d));
cout << d[k - 1] * ot << endl;
return 0;
}
ld best = 2e18;
mt19937_64 rng(0);
shuffle(ps.begin(), ps.end(), rng);
ld eps1 = 1e-7;
ld eps2 = 1e-7;
FOR(i,n) FOR(j,i) {
if(i == j) continue;
Pd mp = (ps[i]+ps[j])/2;
Pd dir = (ps[j]-ps[i]).perp().unit();
ld mi = -1e9, ma = 1e9;
while(err(mi,ma) > eps2) {
ld md1 = (2*mi + ma)/3;
ld md2 = (mi + 2*ma)/3;
ld c1 = (mp + dir*md1).dist()*s + (mp + dir*md1 - ps[i]).dist()*t;
ld c2 = (mp + dir*md2).dist()*s + (mp + dir*md2 - ps[i]).dist()*t;
//cout << mi << " " << ma << endl;
if(c1 <= c2) {
ma = md2;
} else {
mi = md1;
}
}
cmp[i][j] = (mi + ma)/2;
cb[i][j] = (mp + dir*cmp[i][j]).dist()*s + (mp + dir*cmp[i][j] - ps[i]).dist()*t;
cb[j][i] = cb[i][j];
cmp[j][i] = -cmp[i][j];
}
FOR(i, n){
ld better = best * (1 - eps1);
//ld better = best - eps2;
//if (!sweep(i, better, eps1,0)) continue;
if (!sweep(i, better,eps2)) continue;
//cout << i << endl;
//cout << ps[i] << " " << i << " " << sweep(i, better,eps2) << " " << better << endl;
ld mic = 0, mac = better;
while(err(mic,mac) > eps2) {
ld md = (mic + mac) / 2;
//cout << " " << md << " " << sweep(i, md, eps2) << endl;
if (sweep(i, md, eps2)) {
mac = md;
} else {
//cout << 0 << endl;
mic = md;
}
}
best = (mic + mac) / 2;
}
cout << best * best * acos(-1) << endl;
}
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: 3968kb
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:
12566370614359172464005784192717684736.000000000000
result:
wrong answer 1st numbers differ - expected: '4930145422.6525173', found: '12566370614359171665031181500172730368.0000000', error = '2548884370960037945844695040.0000000'
Subtask #2:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 7ms
memory: 3968kb
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:
5194981132829493394.500000000000
result:
wrong answer 1st numbers differ - expected: '128592913281.7085724', found: '5194981132829493248.0000000', error = '40398657.0617304'
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: 1ms
memory: 3968kb
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:
12566370614359172464005784192717684736.000000000000
result:
wrong answer 1st numbers differ - expected: '3882365967.1217990', found: '12566370614359171665031181500172730368.0000000', error = '3236781571026205598300504064.0000000'
Subtask #7:
score: 0
Skipped
Dependency #1:
0%