QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#786480#4668. Find The Lengthucup-team266#WA 0ms4324kbC++142.1kb2024-11-26 21:44:512024-11-26 21:44:52

Judging History

你现在查看的是最新测评结果

  • [2024-11-26 21:44:52]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4324kb
  • [2024-11-26 21:44:51]
  • 提交

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