QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#658910 | #5667. Meeting Places | ucup-team5234# | WA | 9ms | 3892kb | C++23 | 2.2kb | 2024-10-19 17:54:53 | 2024-10-19 17:54:53 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
ll MOD = 1000000007;
ll INF = (1ll<<60);
using ld = long double;
#define rep(i,n) for(int i=0;i<n;i++)
#define dout(a) cout << fixed << setprecision(20) << a << endl;
ld dis(ld x, ld y) {
return x*x + y*y;
}
static const ld eps = 1e-11;
tuple<ld, ld, ld> solve(vector<pair<ld, ld>> p){
int n = p.size();
ld x = 0, y = 0;
rep(i, n) {
x += p[i].first;
y += p[i].second;
}
x /= ld(n);
y /= ld(n);
ld r = 0.998;
ld d = 1e9;
rep(_, 30000) {
int id = -1;
ld m = -1;
rep(i, n) {
ld ret = dis(x - p[i].first, y - p[i].second);
if(ret > m) {
m = ret;
id = i;
}
}
ld X = p[id].first - x;
ld Y = p[id].second - y;
m = sqrtl(m);
X /= m;
Y /= m;
X *= d;
Y *= d;
x += X;
y += Y;
d *= r;
}
ld m = -eps;
rep(i, n) {
ld ret = dis(x - p[i].first, y - p[i].second);
if(ret > m) {
m = ret;
}
}
return {sqrtl(m), x, y};
}
int main(){
ll n,k,X;
cin >> n >> k >> X;
if(n == k){
cout << 0.0 << endl;
return 0;
}
vector<ld> x(n), y(n);
rep(i,n){
x[i] = X;
X = X*233811181+1;
X %= (1ll<<31)-1;
y[i] = X;
X = X*233811181+1;
X %= (1ll<<31)-1;
}
ld ans = INF;
ld sx, sy, sr;
ld ep = 10;
{
vector<pair<ld, ld>> p;
for(int j=0; j<n-k+1; j++) p.emplace_back(x[j], y[j]);
auto[r, x, y] = solve(p);
ans = min(ans, r);
sx = x, sy = y, sr = r;
}
for(int i=1; i+n-k+1<=n; i++){
ld R = sqrtl(dis(sx - x[i-1], sy - y[i-1]));
ld R2 = sqrtl(dis(sx - x[i+n-k], sy - y[i+n-k]));
if(R > sr - ep || R2 > sr){
vector<pair<ld, ld>> p;
for(int j=i; j<i+n-k+1; j++) p.emplace_back(x[j], y[j]);
auto[a,b,c] = solve(p);
ans = min(ans, a);
sr = a;
sx = b;
sy = c;
}
}
dout(ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 9ms
memory: 3892kb
input:
100 23 213
output:
1319350480.80073253880254924297
result:
ok found '1319350480.8007326', expected '1319350480.8007326', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
10 1 1060
output:
1042753143.34516768663888797164
result:
ok found '1042753143.3451676', expected '1042753143.3451676', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
10 10 2373
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
10 2 3396
output:
1236610536.94692303123883903027
result:
ok found '1236610536.9469230', expected '1236610536.9469230', error '0.0000000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3836kb
input:
10 3 1998
output:
973790809.82244422752410173416
result:
ok found '973790809.8224442', expected '973790809.8224442', error '0.0000000'
Test #6:
score: 0
Accepted
time: 3ms
memory: 3788kb
input:
10 4 562
output:
910867389.90693293767981231213
result:
ok found '910867389.9069330', expected '910867389.9069330', error '0.0000000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3888kb
input:
10 5 6048
output:
818240814.71051498217275366187
result:
ok found '818240814.7105150', expected '818240814.7105150', error '0.0000000'
Test #8:
score: -100
Wrong Answer
time: 4ms
memory: 3892kb
input:
10 6 2524
output:
674787674.31298542517470195889
result:
wrong answer 1st numbers differ - expected: '500106979.3467762', found: '674787674.3129854', error = '0.3492867'