Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <memory.h>
- #include <cstdlib>
- #include <algorithm>
- #include <iostream>
- #include <utility>
- #include <vector>
- #include <set>
- #include <map>
- #include <cmath>
- #include <string>
- #include <ctime>
- using namespace std;
- #define forn( i,n ) for ( int i=0; i<(int)(n); i++ )
- #define pb push_back
- #define mp make_pair
- #define sz(a) (int)((a).size())
- typedef long long ll;
- typedef double ld;
- typedef pair<int,int> pii;
- typedef pair<double,int> pdi;
- const int maxn = 2010;
- const ld PI = acos( -1.0 );
- int n, L, x1[maxn], _y1[maxn], x2[maxn], y2[maxn];
- pdi ev[maxn*2];
- int ke;
- bool getSeg( ld x1, ld _y1, ld x2, ld y2, ld& res ) {
- if ( _y1*y2 > 1e-7 ) return false;
- res = x1 + ( x2-x1 )*fabs( _y1 )/( fabs( _y1 ) + fabs( y2 ) );
- return true;
- }
- bool getCircle( ld xx, ld yy, ld rr, ld& ci, ld& ca ) {
- if ( fabs( yy ) > rr ) return false;
- ld dx = sqrt( rr*rr - yy*yy );
- ci = xx - dx;
- ca = xx + dx;
- return true;
- }
- ld min( ld a, ld b ) {
- return a < b ? a : b;
- }
- ld max( ld a, ld b ) {
- return a > b ? a : b;
- }
- bool check( double R ) {
- ke = 0;
- forn( i, n ) {
- ld mi = 1e9;
- ld ma = -1e9;
- ld ci, ca;
- if ( getCircle( x1[i], _y1[i], R, ci, ca ) ) {
- mi = min( mi, ci );
- ma = max( ma, ca );
- }
- if ( getCircle( x2[i], y2[i], R, ci, ca ) ) {
- mi = min( mi, ci );
- ma = max( ma, ca );
- }
- ld an = atan2( y2[i]-_y1[i], x2[i]-x1[i] ) - PI/2;
- ld dx = R * cos( an );
- ld dy = R * sin( an );
- if ( _y1[i] > y2[i] ) {
- if ( getSeg( x1[i]+dx, _y1[i]+dy,
- x2[i]+dx, y2[i]+dy, ci ) ) mi = min( mi, ci );
- if ( getSeg( x1[i]-dx, _y1[i]-dy,
- x2[i]-dx, y2[i]-dy, ca ) ) ma = max( ma, ca );
- }
- else
- {
- if ( getSeg( x1[i]+dx, _y1[i]+dy,
- x2[i]+dx, y2[i]+dy, ca ) ) ma = max( ma, ca );
- if ( getSeg( x1[i]-dx, _y1[i]-dy,
- x2[i]-dx, y2[i]-dy, ci ) ) mi = min( mi, ci );
- }
- if ( mi < 1e8 ) {
- ev[ke++] = pdi( max( mi, 0.0 ), -1 );
- ev[ke++] = pdi( min( ma, 1.0*L ), +1 );
- }
- }
- sort( ev, ev+ke );
- int bal = 0;
- if ( ke == 0 || ev[0].first > 1e-7 ) return true;
- forn( i, ke ) {
- bal += ev[i].second;
- if ( bal == 0 && ( i < ke-1 || ev[i].first < L-1e-7 ) ) return true;
- }
- return false;
- }
- int main()
- {
- freopen( "c.in", "r", stdin );
- int tc;
- scanf( "%d", &tc );
- while ( tc-- ) {
- scanf( "%d %d", &n, &L );
- forn( i, n ) {
- scanf( "%d %d %d %d", &x1[i], &_y1[i], &x2[i], &y2[i] );
- if ( x1[i] > x2[i] ) {
- swap( x1[i], x2[i] );
- swap( _y1[i], y2[i] );
- }
- }
- double l = 0, r = L, m;
- forn( it, 500 ) {
- m = ( l+r ) * 0.5;
- if ( check( m ) ) l = m;
- else r = m;
- }
- printf( "%.3f\n", l );
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement