QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786657 | #4668. Find The Length | ucup-team266# | WA | 0ms | 4124kb | C++14 | 2.7kb | 2024-11-26 22:41:08 | 2024-11-26 22:41:10 |
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;
typedef long double ld;
const ld 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); }
ld len(vec v){ return sqrt(1. * v.x * v.x + 1. * v.y * v.y); }
const ld pi = acos(-1);
int n, R;
vec O[111]; int rs[111];
typedef pair<ld, ld> pdd;
vector<pdd> inter(vector<pdd> &a, vector<pdd> &b){
//cout << "---------- inter ------------\n";
//for(auto &p : a) cout << p.first << " " << p.second << "; "; cout << endl;
//for(auto &p : b) cout << p.first << " " << p.second << "; "; cout << endl;
vector<pdd> ret;
int j = 0;
rep(i, (int)a.size()){
while(j < (int)b.size() && b[j].second < a[i].first) ++j;
while(j < (int)b.size()){
ret.push_back(make_pair(max(a[i].first, b[j].first), min(a[i].second, b[j].second)));
if(b[j].second < a[i].second) ++j;
else break;
}
}
//for(auto &p : ret) cout << p.first << " " << p.second << "; "; cout << endl;
return ret;
}
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];
ld ans = 0, sum = 0; bool has = 0;
rep(i, n){
vector< pdd > cur;
cur.push_back(make_pair(-pi, pi));
rep(j, n) if(j != i){
vec d = O[j] - O[i];
ld 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){
cur.clear();
break;
}
ld ang = acos((a*a + b*b - c*c) / (2. * a * b));
ld t = atan2(d.y, d.x);
//cout << " " << j << " " << t << " " << ang << endl;
ld l = t - ang, r = t + ang;
if(l < -pi-eps) l += 2.*pi;
if(r > pi+eps) r -= 2.*pi;
vector<pdd> nxt;
if(l > r) nxt.push_back(make_pair(-pi, r)), nxt.push_back(make_pair(l, pi));
else nxt.push_back(make_pair(l, r));
cur = inter(cur, nxt);
}
if(cur.empty()) continue;
//cout << i << ": "; for(auto &p : cur) cout << p.first << " " << p.second << "; ";
//cout << endl;
ld curlen = 0;
for(auto &p : cur) curlen += p.second - p.first;
ans += curlen * (2. * R - rs[i]), sum += curlen; 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: 3876kb
input:
1 5 0 0 3
output:
43.982297150257
result:
ok
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 4124kb
input:
4 8 -1 -1 3 -1 -1 1 6 -3 1 2 2 2
output:
40.951919331912
result:
wrong answer read 40.951919332 but expected 69.138911696, error = 0.407686376