fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define LL long long
  3. #define FOR(i,c) for(__typeof(c.begin()) i = c.begin(); i != c.end(); i++)
  4. #define F first
  5. #define S second
  6. using namespace std;
  7.  
  8. const LL mod = 1e9 + 7;
  9.  
  10. template<typename T> T gcd(T a, T b) { return b == 0?a: gcd(b, a % b); }
  11. template<typename T> T LCM(T a, T b) { return a*(b/gcd(a, b)); }
  12. template<typename T> T expo(T base, T e, T mod) { T res = 1;
  13.   while(e > 0) { if(e&1) res = res * base % mod; base = base * base % mod; e >>= 1; }
  14.   return res;
  15. }
  16. template<typename T, typename S> T expo(T b, S e){if(e <= 1)return e == 0?1: b;\
  17. 	return (e&1) == 0?expo((b*b), e>>1): (b*expo((b*b), e>>1));}
  18. template<typename T, typename S> T modinv(T a, S mod) { return expo(a, mod-2, mod); }
  19. template<class T, class S> std::ostream& operator<<(std::ostream &os, const std::pair<T, S> &t) {
  20. 	os<<"("<<t.first<<", "<<t.second<<")";
  21. 	return os;
  22. }
  23. template<class T> std::ostream& operator<<(std::ostream &os, const std::vector<T> &t) {
  24. 	os<<"["; FOR(it,t) { if(it != t.begin()) os<<", "; os<<*it; } os<<"]";
  25. 	return os;
  26. }
  27.  
  28. const int MAXN = 11;
  29. const int ACC = 50;
  30. const double EPS = 1e-7;
  31.  
  32. int n;
  33. double P, H;
  34. double x[MAXN], y[MAXN];
  35.  
  36. double dist(double x1, double y1, double x2, double y2) {
  37. 	return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
  38. }
  39. double dist(pair<double, double> a, pair<double, double> b) {
  40. 	return sqrt((a.F - b.F)*(a.F - b.F) + (a.S - b.S)*(a.S - b.S));
  41. }
  42.  
  43. double dist_at(double a, double x, double cx, double cy) {
  44. 	double y = a * x * (x - P);
  45. 	return dist(x, y, cx, cy);
  46. }
  47.  
  48. pair<double, double> closest(double a, double cx, double cy) {
  49. 	pair<double, double> res;
  50. 	double lower = 0, upper = P, f1, f2;
  51. 	if(fabs(cx - P/2.0l) < EPS) {
  52. 		lower = 0, upper = P/2.0l;
  53. 	}
  54. 	for(int i = 0; i < ACC; i++) {
  55. 		f1 = lower + (upper - lower)/3.0l;
  56. 		f2 = f1 + (upper - lower)/3.0l;
  57. 		if(dist_at(a, f1, cx, cy) < dist_at(a, f2, cx, cy)) {
  58. 			upper = f2;
  59. 		} else {
  60. 			lower = f1;
  61. 		}
  62. 	}
  63. 	res.F = (lower + upper)/2;
  64. 	res.S = a * res.F * (res.F - P);
  65. 	return res;
  66. }
  67.  
  68. // Open = -1
  69. // Close = 1
  70. bool fixR(double r) {
  71. 	vector<pair<double, int> > events;
  72. 	for(int i = 0; i < n; i++) {
  73. 		double curr_x = x[i], curr_y = y[i];
  74. 		double lower = - (curr_y / (curr_x * (P - curr_x))), upper = 0, a;
  75. 		for(int iter = 0; iter < ACC; iter++) {
  76. 			a = (lower + upper) / 2.0l;
  77. 			// Given a, and center of circle, find closest point on parabola
  78. 			pair<double, double> onp = closest(a, curr_x, curr_y);
  79. 			double D = dist(onp.F, onp.S, curr_x, curr_y);
  80. 			if(D < r) {
  81. 				lower = a;
  82. 			} else {
  83. 				upper = a;
  84. 			}
  85. 		}
  86. 		a = (lower + upper) / 2.0l;
  87. 		if(fabs(dist(closest(a, curr_x, curr_y), {curr_x, curr_y}) - r) < EPS) {
  88. 			events.push_back({0.0l, -1});
  89. 			events.push_back({a, 1});
  90. 		}
  91. 		lower = 4.0l * (r - H) / (P*P), upper = - (curr_y / (curr_x * (P - curr_x)));
  92. 		if(lower <= upper) {
  93. 			for(int iter = 0; iter < ACC; iter++) {
  94. 				a = (lower + upper) / 2.0l;
  95. 				pair<double, double> onp = closest(a, curr_x, curr_y);
  96. 				double D = dist(onp.F, onp.S, curr_x, curr_y);
  97. 				if(D < r) {
  98. 					upper = a;
  99. 				} else {
  100. 					lower = a;
  101. 				}
  102. 			}
  103. 			a = (lower + upper) / 2.0l;
  104. 			if(fabs(dist(closest(a, curr_x, curr_y), {curr_x, curr_y}) - r) < EPS) {
  105. 				events.push_back({a, -1});
  106. 				events.push_back({4.0l * (r - H) / (P*P), 1});
  107. 			}
  108. 		}
  109. 	}
  110. 	int have = 0;
  111. 	sort(events.begin(), events.end(), [&](const pair<double, int> &lhs,
  112. 								const pair<double, int> &rhs) {
  113. 				if(fabs(lhs.F - rhs.F) < EPS) return lhs.S < rhs.S;
  114. 				return lhs.F > rhs.F;
  115. 			});
  116. 	for(auto &elem: events) {
  117. 		have += elem.S;
  118. 		if(have == -n) {
  119. 			return true;
  120. 		}
  121. 	}
  122. 	return false;
  123. }
  124.  
  125. int main() {
  126.   ios_base::sync_with_stdio(false);
  127. 	int t;
  128. 	cin >> t;
  129. 	for(int tc = 1; tc <= t; tc++) {
  130. 		cout << "Case #" << tc << ": ";
  131. 		cin >> n >> P >> H;
  132. 		for(int i = 0; i < n; i++) {
  133. 			cin >> x[i] >> y[i];
  134. 		}
  135. 		double lower = 0, upper = H, mid;
  136. 		for(int i1 = 0; i1 < ACC; i1++) {
  137. 			mid = (lower + upper) / 2.0l;
  138. 			if(fixR(mid)) {
  139. 				lower = mid;
  140. 			} else {
  141. 				upper = mid;
  142. 			}
  143. 		}
  144. 		mid = (lower + upper) / 2.0l;
  145. 		cout << setprecision(8) << fixed << mid << '\n';
  146. 	}
  147.   return 0;
  148. }
  149.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gEFpNO
language:
C++14 (clang 8.0)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!