Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<cstdio>
- #include<vector>
- #include<algorithm>
- #include<queue>
- using namespace std;
- vector< pair<double,double> > X, Y;
- /*inline int max( queue < pair< double, double > > a, int b )
- {
- int rozm = a.size();
- if( rozm > b ) return rozm;
- else return b;
- }*/
- inline int czytaj()
- {
- int n;
- scanf("%d",&n);
- for( int i = 0 ; i < n ; ++i)
- {
- pair< double, double > tmp;
- scanf("%lf %lf",&tmp.first,&tmp.second);
- X.push_back(tmp);
- double tmp2 = tmp.first;
- tmp.first = tmp.second;
- tmp.second = tmp2;
- Y.push_back(tmp);
- }
- return n;
- }
- void odpo( double d, int n )
- {
- /*list*/queue< pair< double, double > > tmp;
- bool znaleziono = false;
- int xp = 0, xk = 0, yp = 0, yk = 0;
- while( xk < n )
- {
- yp = 0; yk = 0;
- while(xk + 1 < n && X[xp].first+d >= X[xk+1].first ) ++xk;
- while( yk < n)
- {
- while( yk < n && Y[yp].first+d >= Y[yk].first)
- {
- if( Y[yk].second >= X[xp].first && Y[yk].second <= X[xk].first ) tmp.push/*_back*/( Y[yk] );
- ++yk;
- }
- if( (int)(tmp.size()) >= (n+1)/2 )
- {
- znaleziono = true;
- break;
- }
- ++yp;
- while(!tmp.empty() && tmp.front().first < Y[yp].first ) tmp.pop/*_front*/();
- }
- if( znaleziono == true ) break;
- //tmp.clear();
- while( ! tmp.empty() ) tmp.pop();
- ++xp;
- if( xk < xp ) xk = xp;
- }
- double x=50, y=50;
- while(!tmp.empty())
- {
- x=min(x,tmp.front().second);
- y=min(y,tmp.front().first);
- tmp.pop/*_front*/();
- }
- if (x + d > 50 ) x=50 - d;
- if (y + d > 50 ) y=50 - d;
- printf("%lf %lf\n", x, y );
- printf("%lf %lf\n", x+d, y+d );
- }
- int ile_max( double d, int n )
- {
- /*list*/queue< pair< double, double > > tmp;
- int xp = 0, xk = 0, yp = 0, yk = 0, ile = 0;
- while( xk < n )
- {
- yp = 0; yk = 0;
- while(xk < n-1 && X[xp].first+d >= X[xk+1].first ) ++xk;
- while( yk < n)
- {
- while( yk < n && Y[yp].first+d >= Y[yk].first)
- {
- if( Y[yk].second >= X[xp].first && Y[yk].second <= X[xk].first ) tmp.push/*_back*/( Y[yk] );
- ++yk;
- }
- //ile = max( tmp, ile );
- int ile2 = tmp.size();
- ile = max( ile, ile2 );
- ++yp;
- while(!tmp.empty() && tmp.front().first < Y[yp].first ) tmp.pop/*_front*/();
- }
- //tmp.clear();
- while( ! tmp.empty() ) tmp.pop();
- ++xp;
- if( xk < xp ) xk = xp;
- }
- return ile;
- }
- int main()
- {
- int Z;
- scanf("%d", &Z);
- while(Z--)
- {
- int n = czytaj();
- int trzeba = n/2 + n % 2;
- sort(X.begin(),X.end()); sort(Y.begin(),Y.end());
- double i=0, j=50;
- while(j-i>1e-7)
- {
- double s = ( i + j ) / 2;
- if( ile_max(s,n) >= trzeba ) j = s;
- else i = s;
- }
- odpo( j, n);
- X.clear();
- Y.clear();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement