Advertisement
Guest User

Untitled

a guest
Jul 22nd, 2017
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.70 KB | None | 0 0
  1. #include<cstdio>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<queue>
  5. using namespace std;
  6. vector< pair<double,double> > X, Y;
  7. /*inline int max( queue < pair< double, double > > a, int b )
  8. {
  9. int rozm = a.size();
  10. if( rozm > b ) return rozm;
  11. else return b;
  12. }*/
  13. inline int czytaj()
  14. {
  15. int n;
  16. scanf("%d",&n);
  17. for( int i = 0 ; i < n ; ++i)
  18. {
  19. pair< double, double > tmp;
  20. scanf("%lf %lf",&tmp.first,&tmp.second);
  21. X.push_back(tmp);
  22. double tmp2 = tmp.first;
  23. tmp.first = tmp.second;
  24. tmp.second = tmp2;
  25. Y.push_back(tmp);
  26. }
  27. return n;
  28. }
  29.  
  30. void odpo( double d, int n )
  31. {
  32. /*list*/queue< pair< double, double > > tmp;
  33. bool znaleziono = false;
  34. int xp = 0, xk = 0, yp = 0, yk = 0;
  35. while( xk < n )
  36. {
  37. yp = 0; yk = 0;
  38. while(xk + 1 < n && X[xp].first+d >= X[xk+1].first ) ++xk;
  39. while( yk < n)
  40. {
  41. while( yk < n && Y[yp].first+d >= Y[yk].first)
  42. {
  43. if( Y[yk].second >= X[xp].first && Y[yk].second <= X[xk].first ) tmp.push/*_back*/( Y[yk] );
  44. ++yk;
  45. }
  46. if( (int)(tmp.size()) >= (n+1)/2 )
  47. {
  48. znaleziono = true;
  49. break;
  50. }
  51. ++yp;
  52. while(!tmp.empty() && tmp.front().first < Y[yp].first ) tmp.pop/*_front*/();
  53. }
  54. if( znaleziono == true ) break;
  55. //tmp.clear();
  56. while( ! tmp.empty() ) tmp.pop();
  57. ++xp;
  58. if( xk < xp ) xk = xp;
  59. }
  60. double x=50, y=50;
  61. while(!tmp.empty())
  62. {
  63. x=min(x,tmp.front().second);
  64. y=min(y,tmp.front().first);
  65. tmp.pop/*_front*/();
  66. }
  67. if (x + d > 50 ) x=50 - d;
  68. if (y + d > 50 ) y=50 - d;
  69. printf("%lf %lf\n", x, y );
  70. printf("%lf %lf\n", x+d, y+d );
  71.  
  72. }
  73.  
  74. int ile_max( double d, int n )
  75. {
  76. /*list*/queue< pair< double, double > > tmp;
  77. int xp = 0, xk = 0, yp = 0, yk = 0, ile = 0;
  78. while( xk < n )
  79. {
  80. yp = 0; yk = 0;
  81. while(xk < n-1 && X[xp].first+d >= X[xk+1].first ) ++xk;
  82. while( yk < n)
  83. {
  84. while( yk < n && Y[yp].first+d >= Y[yk].first)
  85. {
  86. if( Y[yk].second >= X[xp].first && Y[yk].second <= X[xk].first ) tmp.push/*_back*/( Y[yk] );
  87. ++yk;
  88. }
  89. //ile = max( tmp, ile );
  90. int ile2 = tmp.size();
  91. ile = max( ile, ile2 );
  92. ++yp;
  93. while(!tmp.empty() && tmp.front().first < Y[yp].first ) tmp.pop/*_front*/();
  94. }
  95. //tmp.clear();
  96. while( ! tmp.empty() ) tmp.pop();
  97. ++xp;
  98. if( xk < xp ) xk = xp;
  99. }
  100. return ile;
  101. }
  102. int main()
  103. {
  104. int Z;
  105. scanf("%d", &Z);
  106. while(Z--)
  107. {
  108. int n = czytaj();
  109. int trzeba = n/2 + n % 2;
  110. sort(X.begin(),X.end()); sort(Y.begin(),Y.end());
  111. double i=0, j=50;
  112. while(j-i>1e-7)
  113. {
  114. double s = ( i + j ) / 2;
  115. if( ile_max(s,n) >= trzeba ) j = s;
  116. else i = s;
  117. }
  118. odpo( j, n);
  119. X.clear();
  120. Y.clear();
  121. }
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement