Advertisement
Guest User

Untitled

a guest
Aug 9th, 2017
223
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
BOO 2.90 KB | None | 0 0
  1. #include <cstdio>
  2. #include <memory.h>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <utility>
  7. #include <vector>
  8. #include <set>
  9. #include <map>
  10. #include <cmath>
  11. #include <string>
  12. #include <ctime>
  13.  
  14. using namespace std;
  15.  
  16. #define forn( i,n ) for ( int i=0; i<(int)(n); i++ )
  17. #define pb push_back
  18. #define mp make_pair
  19. #define sz(a) (int)((a).size())
  20. typedef long long ll;
  21. typedef double ld;
  22. typedef pair<int,int> pii;
  23. typedef pair<double,int> pdi;
  24.  
  25. const int maxn = 2010;
  26. const ld PI = acos( -1.0 );
  27.  
  28. int n, L, x1[maxn], _y1[maxn], x2[maxn], y2[maxn];
  29. pdi ev[maxn*2];
  30. int ke;
  31.  
  32. bool getSeg( ld x1, ld _y1, ld x2, ld y2, ld& res ) {  
  33.   if ( _y1*y2 > 1e-7 ) return false;
  34.   res = x1 + ( x2-x1 )*fabs( _y1 )/( fabs( _y1 ) + fabs( y2 ) );
  35.   return true;
  36. }
  37.  
  38. bool getCircle( ld xx, ld yy, ld rr, ld& ci, ld& ca ) {
  39.   if ( fabs( yy ) > rr ) return false;
  40.   ld dx = sqrt( rr*rr - yy*yy );
  41.   ci = xx - dx;
  42.   ca = xx + dx;
  43.   return true;
  44. }
  45.  
  46. ld min( ld a, ld b ) {
  47.   return a < b ? a : b;
  48. }
  49.  
  50. ld max( ld a, ld b ) {
  51.   return a > b ? a : b;
  52. }
  53.  
  54. bool check( double R ) {
  55.   ke = 0;
  56.   forn( i, n ) {
  57.     ld mi = 1e9;
  58.     ld ma = -1e9;
  59.     ld ci, ca;
  60.     if ( getCircle( x1[i], _y1[i], R, ci, ca ) ) {
  61.       mi = min( mi, ci );
  62.       ma = max( ma, ca );
  63.     }
  64.    
  65.     if ( getCircle( x2[i], y2[i], R, ci, ca ) ) {
  66.       mi = min( mi, ci );
  67.       ma = max( ma, ca );
  68.     }
  69.    
  70.     ld an = atan2( y2[i]-_y1[i], x2[i]-x1[i] ) - PI/2;
  71.     ld dx = R * cos( an );
  72.     ld dy = R * sin( an );
  73.     if ( _y1[i] > y2[i] ) {
  74.       if ( getSeg( x1[i]+dx, _y1[i]+dy,
  75.                    x2[i]+dx, y2[i]+dy, ci ) ) mi = min( mi, ci );
  76.       if ( getSeg( x1[i]-dx, _y1[i]-dy,
  77.                    x2[i]-dx, y2[i]-dy, ca ) ) ma = max( ma, ca );
  78.     }
  79.     else
  80.     {
  81.       if ( getSeg( x1[i]+dx, _y1[i]+dy,
  82.                    x2[i]+dx, y2[i]+dy, ca ) ) ma = max( ma, ca );
  83.       if ( getSeg( x1[i]-dx, _y1[i]-dy,
  84.                    x2[i]-dx, y2[i]-dy, ci ) ) mi = min( mi, ci );
  85.     }
  86.    
  87.     if ( mi < 1e8 ) {
  88.       ev[ke++] = pdi( max( mi, 0.0 ), -1 );
  89.       ev[ke++] = pdi( min( ma, 1.0*L ), +1 );
  90.     }
  91.   }
  92.  
  93.   sort( ev, ev+ke );
  94.  
  95.   int bal = 0;
  96.   if ( ke == 0 || ev[0].first > 1e-7 ) return true;
  97.   forn( i, ke ) {
  98.     bal += ev[i].second;
  99.     if ( bal == 0 && ( i < ke-1 || ev[i].first < L-1e-7 ) ) return true;
  100.   }
  101.  
  102.   return false;
  103. }
  104.  
  105. int main()
  106. {
  107.   freopen( "c.in", "r", stdin );
  108.  
  109.   int tc;
  110.   scanf( "%d", &tc );
  111.   while ( tc-- ) {
  112.     scanf( "%d %d", &n, &L );
  113.     forn( i, n ) {
  114.       scanf( "%d %d %d %d", &x1[i], &_y1[i], &x2[i], &y2[i] );
  115.       if ( x1[i] > x2[i] ) {
  116.         swap( x1[i], x2[i] );
  117.         swap( _y1[i], y2[i] );
  118.       }
  119.     }
  120.      
  121.     double l = 0, r = L, m;
  122.     forn( it, 500 ) {
  123.       m = ( l+r ) * 0.5;
  124.       if ( check( m ) ) l = m;
  125.       else r = m;
  126.     }
  127.      
  128.     printf( "%.3f\n", l );
  129.   }
  130.  
  131.   return 0;
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement