0
Your rating: None

CodeChef submission 107851 (C++ 4.0.0-8)

CodeChef submission 107851 (C++ 4.0.0-8) plaintext list. Status: TLE, problem H2, contest OCT09. By pmnox (pmnox), 2009-10-10 21:13:15.
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <string>
  7. #include <numeric>
  8. #include <cmath>
  9. #include <cstdlib>
  10. #include <iostream>
  11. #include <sstream>
  12. #include <cstring>
  13. using namespace std;
  14.  
  15. #define rep(i,b) for(int i=(0);i<(b);++i)
  16. #define fo(i,a,b) for(int i=(a);i<=(b);++i)
  17. #define ford(i,a,b) for(int i=(a);i>=(b);--i)
  18. #define fore(a,b) for(__typeof((b).begin()) a = (b).begin();a!=(b).end();++a)
  19. #define vv vector
  20. #define pb push_back
  21. #define ll long long
  22. #define ld long double
  23. #define ss(a) (int)(a).size()
  24. #define all(x) (x).begin(),(x).end()
  25. #define clr(x,a) memset(x,a,sizeof(x))
  26. #define vi vv<int>
  27. #define vs vv<string>
  28.  
  29. int cond = (ll)1;
  30. #define db(x) { if (cond > 0) { cond--; rep (xxx, 1) cerr << __LINE__ << " " << #x << " " << x << endl; cerr.flush(); } }
  31.  
  32. const int sz = 100011;
  33.  
  34. int w[sz];
  35. int h[sz];
  36.  
  37. int n;
  38.  
  39. bool can(ld mid) {
  40. 	vv<ld> val;
  41. 	rep (i, n) val.pb( w[i] - h[i]/mid + 10);
  42. 	sort(all(val));
  43. 	rep (i, n/2) if (val[i] + val[n-1-i] > 0) return 0;
  44. 	return 1;
  45. }
  46.  
  47. void solve() {
  48. 	scanf("%d", &n);
  49. 	rep (i, n) {
  50. 		scanf("%d%d", &w[i], &h[i]);
  51. 	}
  52. 	ld le = 0;
  53. 	ld ri = 10;
  54. 	rep (i, 200) {
  55. 		ld mid = (le + ri) / 2;
  56. 		if (can(mid))
  57. 			le = mid;
  58. 		else
  59. 			ri = mid;
  60. 	}
  61. 	printf("%.9lf\n", (double)le);
  62. }
  63.  
  64. int main(int argc, char ** argv) {
  65.     ios::sync_with_stdio(false);
  66.     cond = argc >= 2 && argv[1][0] == 'q' ? 1 << 30 : 0;
  67.     solve();
  68.     return 0;
  69. }
  70.  
  71.

Comments