Clocks Gym - 101078E

E Clocks

题目链接：https://cn.vjudge.net/problem/Gym-101078E

Problem

During the past few years Tim E. has been collecting circle-shaped clocks and he exposed them

on a big wall in his living room. He wants to buy another big clock, but because his wall is almost

full he wants to know what the radius of the biggest clock is that could be exposed on the wall

without overlapping any other clock.

The wall is modelled as a rectangle with width W and height H. For each clock the coordinates

(xi

,yi) of the centre-point and the radius ri are given. The clocks will not overlap with the

boundaries of the wall, nor will two clocks overlap, however they might touch each other.

Input

The first line of the input contains a single number: the number of test cases to follow. Each test

case has the following format:

• One line with two integers W and H satisfying 1 ≤ W,H ≤ 1, 000, 000: the width and the

height of the wall, respectively.

• One line with an integer C satisfying 0 ≤ C ≤ 50: the number of clocks.

• C lines, each with three integers xi, yi and ri satisfying ri > 0, 0 ≤ xi − ri, xi + ri ≤ W,0 ≤ yi − ri and yi + ri ≤ H: the location and radius of an existing clock.Integers on the same line are separated by single spaces. For any pair of clocks i and j (i != j),(xi − xj )^2 + (yi − yj )^2 ≥ (ri + rj )^2

.

Output

For every test case in the input, the output should contain a single real number, on a single line:

the maximum radius of a clock that fits on the wall without overlapping with any existing clock

or the boundaries of the wall.

Your answer should have either an absolute or a relative error of at most 10−6

. Make

sure that you print enough decimals. In particular, if you program in C++, do not use plain

cout << M << endl; to output your answer (a double) M, because this sometimes produces

too few decimals. Instead, you may use printf (“%lf\n”, M); .

Example

Input

1

10 10

4

2 2 1

2 8 1

8 2 1

8 8 1

Output

3.242640687119285

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<cmath>

using namespace std;
double w,h,xx;
int n;
struct node{
    double x,y;
    double r;
}a[];
int check(double x,double y,double r,int c1,int c2)
{
    if(x-r<||x+r>w||y-r<||y+r>h)
        return ;
    double tx,ty,tr;
    for(int i=;i<n;i++)
    {
        tx=a[i].x;
        ty=a[i].y;
        tr=a[i].r;
        if(i!=c1&&i!=c2&&sqrt((ty-y)*(ty-y)+(tx-x)*(tx-x))<r+tr)
            return ;
    }
    return ;
}

int check1(double r)
{
    if(check(r,r,r,-,-))   return ;
    if(check(w-r,r,r,-,-)) return ;
    if(check(w-r,h-r,r,-,-)) return ;
    if(check(r,h-r,r,-,-)) return ;
    return ;

}

int check2(double r)
{

    for(int i=;i<n;i++)
    {
        double tx=a[i].x;
        double ty=a[i].y;
        double tr=a[i].r;
        double r2=(tr+r)*(tr+r);
        double tmp;

        if(*r+tr>=ty){
            tmp=sqrt(r2-(ty-r)*(ty-r));
            if(check(tx+tmp,r,r,i,-))  return ;
            if(check(tx-tmp,r,r,i,-)) return ;
        }
        if(*r+tr>=tx){
            tmp=sqrt(r2-(tx-r)*(tx-r));
            if(check(r,ty+tmp,r,i,-)) return ;
            if(check(r,ty-tmp,r,i,-)) return ;
        }
        if(*r+tr>=h-ty){
            tmp=sqrt(r2-(h-ty-r)*(h-ty-r));
            if(check(tx+tmp,h-r,r,i,-)) return ;
            if(check(tx-tmp,h-r,r,i,-)) return ;
        }
        if(*r+tr>=w-tx){
            tmp=sqrt(r2-(w-tx-r)*(w-tx-r));
            if(check(w-r,ty+tmp,r,-,i)) return ;
            if(check(w-r,ty-tmp,r,-,i)) return ;
        }
    }
    return ;
}

int check3(double r)
{
    double r1,r2,dx,dy,d,aa,x3,y3,g,rx,ry;
    for(int i=;i<n;i++)
        for(int j=i+;j<n;j++)
        {
            r1 = a[i].r+r;
            r2 = a[j].r + r;
            dx = a[j].x - a[i].x;
            dy = a[j].y - a[i].y;
            d = sqrt(dx * dx + dy * dy);
            if (d > r1 + r2)
                continue;
            aa = ((r1 * r1) - (r2 * r2) + (d * d)) / ( * d);
            x3 = a[i].x + (dx * aa / d);
            y3 =a[i].y + (dy * aa / d);
            g = sqrt((r1 * r1) - (aa * aa));
            rx = -dy * (g / d);
            ry = dx * (g / d);
            if(check(x3+rx,y3+ry,r,i,j)||check(x3-rx,y3-ry,r,i,j))
                return ;
        }
    return ;

}
double  chazhao()
{
    double l=;
    double r=xx;
    double m;
    while(r-l>)
    {
        m=(l+r)/;
        if(check1(m)||check2(m)||check3(m))
            l=m;
        else
            r=m;
    }
    return l;
}
int main()
{
    int t;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%d",&w,&h,&n);
        for(int i=;i<n;i++)
        {
            scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r);
        }
        xx=(double)min(w,h)/;
        double res=chazhao();
        printf("%lf\n",res);
    }

}