fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. #define sz(st) int(st.size())
  5. #define all(st) st.begin(), st.end()
  6.  
  7. namespace geometry
  8. {
  9. 	// ! Angles are in radians
  10. 	const double EPS = 1E-12, PI = acos(-1.0);
  11. 	typedef complex<double> point;
  12. 	// * points ,lines and vectors are represented by complex numbers
  13. #define X real()
  14. #define Y imag()
  15.  
  16. 	int dblcmp(double a, double b) {
  17. 		return fabs(a - b) < EPS ? 0 : a < b ? -1 : 1;
  18. 	}
  19.  
  20. 	// * Points & Vectors
  21.  
  22. 	double dist(point a, point b) {
  23. 		return hypot(a.X - b.X, a.Y - b.Y);
  24. 	}
  25.  
  26. 	double dot(point a, point b) {
  27. 		return real(conj(a) * b);
  28. 	}
  29.  
  30. 	double cross(point a, point b) {
  31. 		return imag(conj(a) * b);
  32. 	}
  33.  
  34. 	double length(point a)
  35. 	{
  36. 		return hypot(a.X, a.Y);
  37. 	}
  38. 	bool is_collinear(point a, point b, point c) {
  39. 		return dblcmp(cross(b - a, c - a), 0) == 0;
  40. 	}
  41. 	bool is_on_ray(point a, point b, point c) {
  42. 		return dblcmp(dot(b - a, c - a), 0) == 1;
  43. 	}
  44. 	bool is_on_segment(point a, point b, point c) {
  45. 		return dblcmp(abs(a - c) + abs(b - c), abs(a - b)) == 0;
  46. 	}
  47. 	bool vector_intersect(point vec1, point vec2)
  48. 	{
  49. 		return !dblcmp(cross(vec1, vec2), 0);
  50. 	}
  51. 	// * Lines 	
  52. 	bool is_parallel(point a, point b, point c, point d)
  53. 	{
  54. 		return dblcmp(cross(b - a, d - c), 0) == 0;
  55. 	}
  56.  
  57. 	bool line_intersect(point a, point b, point c, point d)
  58. 	{
  59. 		if (is_parallel(a, b, c, d)) return false;
  60. 		double a1 = cross(d - c, a - c);
  61. 		double a2 = cross(d - c, b - c);
  62. 		if ((a1 > 0 && a2 > 0) || (a1 < 0 && a2 < 0)) return false;
  63. 		a1 = cross(b - a, c - a);
  64. 		a2 = cross(b - a, d - a);
  65. 		if ((a1 > 0 && a2 > 0) || (a1 < 0 && a2 < 0)) return false;
  66. 		return true;
  67. 	}
  68.  
  69. 	bool is_perpendicular(point a, point b, point c, point d)
  70. 	{
  71. 		return dblcmp(dot(b - a, d - c), 0) == 0;
  72. 	}
  73.  
  74. 	bool is_coincide(point a, point b, point c, point d) {
  75. 		return is_parallel(a, b, c, d) && is_parallel(a, c, a, d);
  76. 	}
  77.  
  78. 	point get_intersection(point a, point b, point c, point d) {
  79. 		if (is_parallel(a, b, c, d)) return point(nan(""), nan(""));
  80. 		double a1 = cross(d - c, a - c);
  81. 		double a2 = cross(d - c, b - c);
  82. 		return (a1 * b - a2 * a) / (a1 - a2);
  83. 	}
  84.  
  85. 	point rotate_by(point a, double theta) {
  86. 		return a * polar(1.0, theta);
  87. 	}
  88.  
  89. 	point rotate_around(point a, point b, double theta) {
  90. 		return (a - b) * polar(1.0, theta) + b;
  91. 	}
  92. 	point translate(point a, point b) {
  93. 		return a + b;
  94. 	}
  95. 	int ccw(point p0, point p1, point p2)
  96. 	{
  97. 		point v1(p1 - p0), v2(p2 - p0);
  98. 		if (dblcmp(cross(v1, v2), 0) > 0) return +1; // counter clockwise
  99. 		if (dblcmp(cross(v1, v2), 0) < 0) return -1; // clockwise
  100.  
  101. 		if (dblcmp(v1.X * v2.X, 0) < 0 || dblcmp(v1.Y * v2.Y, 0) < 0) // p2 is behind p1
  102. 			return -1;
  103.  
  104. 		if (dblcmp(norm(v1), norm(v2)) < 0) return +1; // p2 is in front of p1
  105.  
  106. 		return 0; // undefined case (collinear)
  107. 	}
  108.  
  109. 	 // 4th parameter is the closest point
  110.  
  111. 	double dist_to_line(point p, point a, point b, point& c)
  112. 	{
  113. 		point ap = p - a, ab = b - a;
  114. 		double u = dot(ap, ab) / norm(ab);
  115. 		c = translate(a, ab * u);
  116. 		return dist(p, c);
  117. 	}
  118.  
  119. 	double dist_to_segment(point p, point a, point b, point& c)
  120. 	{
  121. 		point ap = p - a, ab = b - a;
  122. 		double u = dot(ap, ab) / norm(ab);
  123. 		if (u < EPS)
  124. 		{
  125. 			c = a;
  126. 			return dist(p, a);
  127. 		}
  128. 		if (u > 1 - EPS)
  129. 		{
  130. 			c = b;
  131. 			return dist(p, b);
  132. 		}
  133. 		return dist_to_line(p, a, b, c);
  134. 	}
  135.  
  136. 	// * Angles
  137. 	double to_rad(double theta) {
  138. 		return theta * PI / 180.0;
  139. 	}
  140.  
  141. 	double to_deg(double theta) {
  142. 		return theta * 180.0 / PI;
  143. 	}
  144.  
  145. 	double fix_angle(double theta) {
  146. 		int sign = (theta < 0 ? -1 : theta > 2.0 * PI ? 1 : 0);
  147. 		return theta + (sign * 2.0 * PI);
  148. 	}
  149.  
  150. 	double angle(point a) {
  151. 		return atan2(imag(a), real(a));
  152. 	}
  153.  
  154. 	double angle(point a, point b) {
  155. 		return fix_angle(angle(b) - angle(a));
  156. 	}
  157.  
  158. 	// * Circles
  159. 	bool is_inside_circle(point center, double radius, point p) {
  160. 		return dblcmp(radius, abs(p - center)) == 1;
  161. 	}
  162.  
  163. 	bool is_on_circle(point center, double radius, point p) {
  164. 		return dblcmp(radius, abs(p - center)) == 0;
  165. 	}
  166. };
  167. using namespace geometry;
  168.  
  169.  
  170. void Solve()
  171. {
  172. 	double x, y;
  173. 	while (cin >> x >> y)
  174. 	{
  175. 		point p(x, y);
  176. 		int n; cin >> n;
  177. 		// 2n + 2 lines of input
  178. 		vector<point> lines;
  179. 		for (int i = 0; i < n + 1; i++)
  180. 		{
  181. 			double x1, y1;
  182. 			cin >> x1 >> y1;
  183. 			lines.push_back(point(x1, y1));
  184. 		}
  185. 		double min_dist = 1e18;
  186. 		point ans;
  187. 		for (int i = 0; i < n; i++)
  188. 		{
  189. 			point a = lines[i], b = lines[i + 1];
  190. 			point c;
  191. 			double d = dist_to_segment(p, a, b, c);
  192. 			if (dblcmp(d, min_dist) == -1)
  193. 			{
  194. 				min_dist = d;
  195. 				ans = c;
  196. 			}
  197. 		}
  198. 		cout << fixed << setprecision(4) << ans.X << "\n" << ans.Y << "\n";
  199. 	}
  200. }
  201.  
  202. signed main()
  203. {
  204. #if LOCAL
  205. 	freopen("input.txt", "r", stdin);
  206. 	freopen("output.txt", "w", stdout);
  207. #endif
  208. 	ios_base::sync_with_stdio(false);
  209. 	cin.tie(nullptr);
  210. 	int t = 1;
  211. 	//cin >> t;
  212. 	for (int tc = 1; tc <= t; tc++) {
  213. 		Solve();
  214. 	}
  215. 	return 0;
  216. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
6
-3
3
0
1
5
5
9
-5
15
3
0
0
1
1
0
2
0
stdout
copy 
7.8966
-2.2414
1.0000
0.0000
https://ideone.com/3Lpa7C
language:
C++ (gcc 8.3)
created:
11 days 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!