QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#786657#4668. Find The Lengthucup-team266#WA 0ms4124kbC++142.7kb2024-11-26 22:41:082024-11-26 22:41:10

Judging History

This is the latest submission verdict.

  • [2024-11-26 22:41:10]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 4124kb
  • [2024-11-26 22:41:08]
  • Submitted

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