QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786480 | #4668. Find The Length | ucup-team266# | WA | 0ms | 4324kb | C++14 | 2.1kb | 2024-11-26 21:44:51 | 2024-11-26 21:44:52 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const double eps = 1e-7;
struct vec{
int x, y;
vec(){ x = y = 0; }
vec(int _x, int _y){ x = _x, y = _y; }
};
inline vec operator + (vec lh, vec rh){ return vec(lh.x + rh.x, lh.y + rh.y); }
inline vec operator - (vec lh, vec rh){ return vec(lh.x - rh.x, lh.y - rh.y); }
double len(vec v){ return sqrt(1. * v.x * v.x + 1. * v.y * v.y); }
const double pi = acos(-1);
int n, R;
vec O[111]; int rs[111];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> R;
rep(i, n) cin >> O[i].x >> O[i].y >> rs[i];
double ans = 0, sum = 0; bool has = 0;
rep(i, n){
double lb = -100, rb = 100;
rep(j, n) if(j != i){
vec d = O[j] - O[i];
double a = len(d), b = R - rs[i], c = R - rs[j];
//cout << i << " " << j << ": " << a << " " << b << " " << c << endl;
if(a > b + c + eps){
cout << "Impossible\n";
return 0;
}
if(c > a + b - eps){
continue;
}
if(b > a + c - eps){
lb = 100;
break;
}
double ang = acos((a*a + b*b - c*c) / (2. * a * b));
double t = atan2(d.y, d.x);
double l = t - ang, r = t + ang;
if(l < -pi-eps) l += 2.*pi;
if(r > pi+eps) r -= 2.*pi;
if(lb < -10) lb = l, rb = r;
else {
if(lb < rb) swap(lb, l), swap(rb, r);
if(lb > rb && l > r){
lb = max(lb, l), rb = min(rb, r);
} else if(lb > rb){
if(r > lb) rb = r;
else if(l < lb) lb = l;
else { lb = 100; break; }
} else {
lb = max(lb, l), rb = min(rb, r);
if(lb > rb){ lb = 100; break; }
}
}
}
if(lb > 10) continue;
double cur = (lb < -10) ? (2.*pi) : ((lb < rb) ? (rb - lb) : ((rb + pi) + (pi - lb)));
//cout << i << ": " << lb << " " << rb << " " << cur << endl;
ans += cur * (2. * R - rs[i]), sum += cur; has = 1;
}
if(!has){
cout << "Impossible\n";
} else {
ans += (2.*pi - sum) * R;
cout << fixed << setprecision(12) << ans << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3868kb
input:
1 5 0 0 3
output:
43.982297150257
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 4236kb
input:
4 8 -1 -1 3 -1 -1 1 6 -3 1 2 2 2
output:
69.138911696387
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
2 10 -8 1 3 8 2 4
output:
Impossible
result:
ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
5 59 -278 -338 32 33 57 48 221 -202 43 -36 -33 33 468 -269 50
output:
Impossible
result:
ok
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 4324kb
input:
5 793 -388 -161 58 319 33 243 -370 -200 207 65 -65 383 409 -461 485
output:
5525.533926941462
result:
wrong answer read 5525.533926941 but expected 5574.694393505, error = 0.008818504