Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define PI 3.14159265
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- const ll N = 1005;
- const ld eps = 1e-4;
- struct pd{
- ld l,r;
- ll id;
- };
- ll n;
- ll x[N],y[N],r[N];
- vector <pd> angles;
- bool cmp(pd prvi,pd drugi){
- if(prvi.l == drugi.l){
- return prvi.r < drugi.r;
- }
- return prvi.l < drugi.l;
- }
- ld getangle(ld x,ld y){
- if(abs(x) <= eps){
- if(y > 0){
- return ld(90);
- }
- return ld(270);
- }
- if(abs(y) <= eps){
- if(x < 0){
- return ld(180);
- }
- return ld(0);
- }
- if(x >= 0 && y >= 0){
- return atan(abs(ld(y)/ld(x)))*180.0 / PI;
- }
- if(x <= 0 && y >= 0){
- return 90.0 - atan(abs(ld(y)/ld(x)))*180.0 / PI +ld(90);
- }
- if(x <= 0 && y <= 0){
- return atan(abs(ld(y)/ld(x)))*180.0 / PI +ld(180);
- }
- if(x >= 0 && y <= 0){
- return 90.0 - atan(abs(ld(y)/ld(x)))*180.0 / PI +ld(270);
- }
- }
- ld razl(ld a,ld b){
- a -= b;
- if(a < 0){
- a += 2*PI;
- }
- return a;
- }
- ld zbir(ld a,ld b){
- a += b;
- if(a >= 2*PI){
- a -= 2*PI;
- }
- return a;
- }
- ll sled(ll x){
- x++;
- if(x == n+1){
- return 1;
- }
- return x;
- }
- bool izmedju(ld levo,ld desno,ld stigo){
- if(levo <= desno){
- return (levo <= stigo && desno >= stigo);
- }
- else{
- return ((levo <= stigo && stigo < 360) || (stigo <= desno));
- }
- }
- void solve(){
- angles.clear();
- for(int i = 1; i <= n; i++){
- cin >> x[i] >> y[i] >> r[i];
- if(x[i] == 0){
- ld dd = sqrt(y[i]*y[i]-r[i]*r[i]);
- ld visina = (dd*ld(r[i]))/y[i];
- ld yo = sqrt(y[i]*y[i]-r[i]*r[i]-visina*visina);
- if(y[i] < 0){
- yo = -yo;
- }
- ld x1 = visina,y1 = yo,x2 = -visina,y2 = yo;
- angles.push_back({getangle(x1,y1),getangle(x2,y2),i});
- }
- else{
- ld dx = x[i];
- ld dy = y[i];
- ld dd = sqrt(dx*dx+dy*dy);
- ld tlen = sqrt(dx*dx+dy*dy-r[i]*r[i]);
- ld a = asin(ld(r[i])/dd);
- ld b = getangle(dx,dy)*PI / 180.0;
- ld t = razl(b,a);
- ld x1 = tlen*cos(t),y1 = tlen*sin(t);
- t = zbir(b,a);
- ld x2 = tlen*cos(t),y2 = tlen*sin(t);
- angles.push_back({getangle(x1,y1),getangle(x2,y2),i});
- }
- }
- sort(angles.begin(),angles.end(),cmp);
- ld sol = 0;
- for(int i = 1; i <= n; i++){
- /// proveri da li je vidljiv
- ld levo = angles[i-1].l,desno = angles[i-1].r;
- ll koji = angles[i-1].id;
- ld stigo = levo;
- ll prvi = 0;
- for(int j = 1; j <= n; j++){
- if(j == i){
- continue;
- }
- ll ind = angles[j-1].id;
- if(x[koji]*x[koji]+y[koji]*y[koji] < x[ind]*x[ind]+y[ind]*y[ind]){
- continue;
- }
- if(izmedju(angles[j-1].l,angles[j-1].r,levo)){
- prvi = j;
- break;
- }
- }
- if(!prvi){
- sol = max(sol,sqrt(ld(x[koji]*x[koji]+y[koji]*y[koji]))-ld(r[koji]));
- continue;
- }
- bool bio = 0;
- bool pokriven = 0;
- for(int j = prvi; ; j=sled(j)){
- if(izmedju(levo,stigo,desno)){
- pokriven = 1;
- break;
- }
- if(bio && j == prvi){
- break;
- }
- bio = 1;
- if(j == i){
- continue;
- }
- ll ind = angles[j-1].id;
- if(x[koji]*x[koji]+y[koji]*y[koji] < x[ind]*x[ind]+y[ind]*y[ind]){
- continue;
- }
- if(izmedju(angles[j-1].l,angles[j-1].r,stigo)){
- stigo = angles[j-1].r;
- }
- }
- if(!pokriven){
- sol = max(sol,sqrt(ld(x[koji]*x[koji]+y[koji]*y[koji]))-ld(r[koji]));
- }
- }
- cout << sol << endl;
- }
- int main(){
- cout.precision(3);
- cout << fixed;
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- while(cin >> n && n){
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement