fork download
copy 
  1. #ifdef PRAGMA_COMMENT_LINKER
  2. #pragma comment(linker, "/STACK:1999999999")
  3. #endif
  4.  
  5. #define  _CRT_SECURE_NO_WARNINGS
  6. #define  NDEBUG
  7.  
  8. #include <algorithm>
  9. #include <cassert>
  10. #include <cctype>
  11. #include <cmath>
  12. #include <cstdio>
  13. #include <cstdlib>
  14. #include <cstring>
  15. #include <ctime>
  16. #include <iomanip>
  17. #include <iostream>
  18. #include <functional>
  19. #include <limits>
  20. #include <list>
  21. #include <map>
  22. #include <memory>
  23. #include <queue>
  24. #include <set>
  25. #include <stack>
  26. #include <string>
  27. #include <utility>
  28. #include <vector>
  29. #include <unordered_map>
  30. #include <unordered_set>
  31.  
  32. using namespace std;
  33.  
  34. #define all(v)                  (v).begin(), (v).end()
  35. #define db(x)                   cout << #x << '=' << (x) << "\n"
  36. #define fend(x)                 ((x) & ((x)+1)) - 1
  37. #define fenu(x)                 (x) | ((x)+1)
  38. #define ft                      first
  39. #define len(s)                  s.length()
  40. #define maxV(type)              std::numeric_limits<type>::max()
  41. #define minV(type)              std::numeric_limits<type>::min()
  42. #define mp(a, b)                std::make_pair((a), (b))
  43. #define ord(c)                  ((c) - 'a' + 1)
  44. #define pob()                   pop_back()
  45. #define pof()                   pop_front()
  46. #define pub(s)                  push_back((s))
  47. #define puf(s)                  push_front((s))
  48. #define sc                      second
  49.  
  50. typedef double                  db;
  51. typedef long double             ld;
  52. typedef long long               ll;
  53. typedef unsigned long long      ull;
  54.  
  55. const   long double				EPS = 1e-15;
  56. const   long double             PI = 3.14159265358979323846;
  57.  
  58. inline int lg2(ll n) { int h = 0; while ((1ll << h) < n) ++h; return h; }
  59.  
  60. struct configio {
  61. 	configio() { cin.tie(nullptr); ios_base::sync_with_stdio(false); }
  62. } cnfio;
  63.  
  64. int diff(int a, int b, int mod) {
  65. 	return ((a - b) % mod + mod) % mod;
  66. }
  67.  
  68. struct line {
  69. 	line() {}
  70. 	line(ld a, ld b, ld c) : a(a), b(b), c(c) {}
  71. 	line(ld x1, ld y1, ld x2, ld y2) {
  72. 		a = y1 - y2;
  73. 		b = x2 - x1;
  74. 		c = -a*x1 - b*y1;
  75. 		ld norm = sqrt(a*a + b*b);
  76. 		a /= norm, b /= norm, c /= norm;
  77. 	}
  78. 	ld dist(ld x, ld y) {
  79. 		ld norm = sqrt(a*a + b*b);
  80. 		return abs(a*x + b*y + c) / norm;
  81. 	}
  82. 	ld a, b, c;
  83. };
  84.  
  85. const int ml = 1e4 + 1;
  86. int n;
  87. int maxid;
  88. ld maxd = -1;
  89. line lines[ml];
  90.  
  91. void max_dist(ld x, ld y) {
  92. 	maxd = -1;
  93. 	for (int i = 0; i < n; ++i) {
  94. 		ld tmp = lines[i].dist(x, y);
  95. 		if (maxd < tmp) {
  96. 			maxd = tmp;
  97. 			maxid = i;
  98. 		}
  99. 	}
  100. }
  101.  
  102. int signum(ld val) {
  103. 	if (val > EPS) return 1;
  104. 	if (val < -EPS) return -1;
  105. 	return 0;
  106. }
  107.  
  108. int main() {
  109. 	//freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
  110. 	cin >> n;
  111. 	for (int i = 0; i < n; i++) {
  112. 		ld  x1, y1, x2, y2;
  113. 		cin >> x1 >> y1 >> x2 >> y2;
  114. 		lines[i] = line(x1, y1, x2, y2);
  115. 	}
  116. 	const int it_lim = 15000;
  117. 	ld step = 1000;
  118. 	ll step_lim = 100000 * 1ll * 100000;
  119. 	ld x = 12, y = 21;
  120. 	for (int i = 0; i < it_lim; ++i) {
  121. 		max_dist(x, y);
  122. 		int old_maxid = maxid;
  123. 		ld old_maxd = maxd;
  124. 		ld tmpx, tmpy;
  125. 		int sgn = signum(lines[maxid].a * x + lines[maxid].b * y + lines[maxid].c);
  126. 		while (true) {
  127. 			tmpx = x - lines[old_maxid].a * step * sgn;
  128. 			tmpy = y - lines[old_maxid].b * step * sgn;
  129. 			max_dist(tmpx, tmpy);
  130. 			if (maxd > old_maxd) {
  131. 				step /= 2;
  132. 			}
  133. 			else {
  134. 				break;
  135. 			}
  136. 		}
  137. 		step *= 2;
  138. 		if (step > step_lim) {
  139. 			step = step_lim;
  140. 		}
  141. 		x = tmpx;
  142. 		y = tmpy;
  143. 	}
  144. 	cout << fixed << setprecision(10);
  145. 	/*max_dist(4040.9996151750674, 12003.999615175067);
  146. 	cout << maxd << endl;
  147. 	max_dist(x, y);
  148. 	cout << maxd << endl;*/
  149. 	cout << x << " " << y << " " << endl;
  150. 	return 0;
  151. }
Success #stdin #stdout 0.02s 3628KB
comments (?)
stdin
copy 
7
376 -9811 376 -4207
6930 -3493 6930 -8337
1963 -251 1963 -5008
-1055 9990 -684 9990
3775 -348 3775 1336
7706 -2550 7706 -8412
-9589 8339 -4875 8339
stdout
copy 
3665.0003848249
3665.0000000000
4041.0000000000 11021.0000000000
https://ideone.com/k5ki3q
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!