Advertisement
cincout

Untitled

Oct 10th, 2019
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.39 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ld = long double;
  6.  
  7. const ld eps = 1e-8;
  8.  
  9. int equal(ld a, ld b) {
  10. return fabs(a - b) < eps;
  11. }
  12.  
  13. struct point {
  14. ld x, y;
  15. point(ld a = 0, ld b = 0) :x(a), y(b) {}
  16. ld len() {
  17. return sqrt(x*x + y*y);
  18. }
  19. };
  20.  
  21. bool operator == (point a, point b) {
  22. return equal(a.x, b.x) && equal(a.y, b.y);
  23. }
  24.  
  25. ld operator * (point a, point b) { return a.x * b.y - b.x * a.y; }
  26. ld operator ^ (point a, point b) {
  27. return a.x * b.x + a.y * b.y;
  28. }
  29.  
  30. point operator - (point a, point b) { return point(a.x - b.x, a.y - b.y); }
  31.  
  32. struct line {
  33. ld a, b, c;
  34. point ff, ss;
  35. line(ld A = 0, ld B = 0, ld C = 0) : a(A), b(B), c(C) {}
  36. line(point f, point s) : a(f.y - s.y), b(s.x - f.x), c(f * s), ff(f), ss(s) {}
  37. bool lay(point a) {
  38. return equal(a.x*a + a.y*b + c, 0.0);
  39. }
  40. };
  41.  
  42. int n;
  43. vector <point> a;
  44.  
  45. point get_point(line b) {
  46. point f;
  47. if (b.b == 0) {
  48. f.x = -b.c / b.a;
  49. f.y = 0;
  50. }
  51. else {
  52. f.x = 0;
  53. f.y = -b.c / b.b;
  54. }
  55. return f;
  56. }
  57.  
  58. point mid(point a, point b) {
  59. return point((a.x + b.x) / 2, (a.y + b.y) / 2);
  60. }
  61.  
  62. bool cross(line a, line b, point &pt) {
  63. ld zn = point(a.a, a.b) * point(b.a, b.b);
  64. if (equal(zn, 0.0)) {
  65. auto f = get_point(b);
  66. if (a.lay(f)) {
  67. pt = f;
  68. return 1;
  69. }
  70. return 0;
  71. }
  72. pt.x = -(point(a.c, a.b) * point(b.c, b.b)) / zn;
  73. pt.y = -(point(a.a, a.c) * point(b.a, b.c)) / zn;
  74. return 1;
  75. }
  76.  
  77. pair<point, ld> get_circle(point a, point b, point c) {
  78. line f(a, b);
  79. line s(b, c);
  80.  
  81. line x(mid(a, b), mid(a, b) - point(f.a, f.b));
  82. line y(mid(b, c), mid(b, c) - point(s.a, s.b));
  83.  
  84. point pt;
  85. cross(x, y, pt);
  86. return make_pair(pt, (pt - a).len());
  87.  
  88. }
  89.  
  90. bool cmp(point a, point b) {
  91. if ((a * b) != 0) {
  92. return (a * b) > 0;
  93. }
  94. return a.len() < b.len();
  95. }
  96.  
  97. vector<point> convex_hull(vector <point> &a) {
  98. int j = -1;
  99. for (int i = 0; i < a.size(); ++i) {
  100. if (j == -1 || (a[i].y < a[j].y || (a[i].y == a[j].y && a[i].x < a[j].x)))
  101. j = i;
  102. }
  103. auto fx = a[j];
  104. for (int i = 0; i < a.size(); ++i) {
  105. a[i] = a[i] - fx;
  106. }
  107. rotate(a.begin(), a.begin() + j, a.end());
  108. sort(a.begin() + 1, a.end(), cmp);
  109. vector<point> hull;
  110. hull.push_back(a[0]);
  111. for (int i = 1; i < a.size(); ++i) {
  112. while (hull.size() > 1) {
  113. auto p1 = a[i] - hull.back();
  114. auto p2 = hull.back() - hull[hull.size() - 2];
  115. if (p2 * p1 > 0) break;
  116. hull.pop_back();
  117. }
  118. hull.push_back(a[i]);
  119. }
  120. fx.x *= -1;
  121. fx.y *= -1;
  122. for (auto &i : hull) {
  123. i = i - fx;
  124. }
  125. return hull;
  126. }
  127.  
  128. ld dist(line a, point b) {
  129. if (a.ff == a.ss) return (a.ff - b).len();
  130. return fabs(a.a * b.x + a.b * b.y + a.c) / sqrt(a.a * a.a + a.b * a.b);
  131. }
  132.  
  133. ld dist(line a, line b) {
  134. if (a.ff == a.ss && b.ff == b.ss) return (a.ff - b.ff).len();
  135. if (a.ff == a.ss) return dist(b, a.ff);
  136. if (b.ff == b.ss) return dist(a, b.ff);
  137. point pt;
  138. if (cross(a, b, pt)) return 0;
  139. return dist(a, get_point(b));
  140. }
  141.  
  142. bool insight_seg(point a, point b, point c) {
  143. return equal((b - a) * (c - a), 0) && ((a - c) ^ (b - c)) <= 0;
  144. }
  145.  
  146. bool insight_ray(point a, point b, point c) {
  147. ld F = ((b - a) ^ (c - a));
  148. return equal((b - a)*(c - a), 0) && ((b - a) ^ (c - a)) >= 0;
  149. }
  150.  
  151. ld dist_to_seg(point a, point b, point c) { // отрезок ab
  152. if (a == b) return (a - c).len();
  153. ld A = (c - a).len();
  154. ld B = (c - b).len();
  155. ld C = (a - b).len();
  156. if (C*C + A*A > B*B && B*B + C*C > A*A) {
  157. return dist(line(a, b), c);
  158. }
  159. return min(A, B);
  160. }
  161.  
  162. void norm(point &a) {
  163. ld h = sqrt(a.x * a.x + a.y*a.y);
  164. a.x /= h;
  165. a.y /= h;
  166. }
  167.  
  168. point operator * (point a, ld k) { return point(a.x * k, a.y * k); }
  169.  
  170. point operator + (point a, point b) { return point(a.x + b.x, a.y + b.y); }
  171.  
  172. point projection(point a, line b) {
  173. point n(b.a, b.b);
  174. norm(n);
  175. ld k = dist(b, a);
  176. auto t1 = a, t2 = a;
  177. t1 = t1 - n * k, t2 = t2 + n * k;
  178. if (dist(b, t1) > dist(b, t2)) swap(t1, t2);
  179. return t1;
  180. }
  181.  
  182. ld dist_to_ray(point a, point b, point c) { // луч ab
  183. if (a == b) return (a - c).len();
  184. auto v = projection(c, line(a, b));
  185. if (insight_ray(a, b, v)) {
  186. return dist(line(a, b), c);
  187. }
  188. return min((c - a).len(), (c - b).len());
  189. }
  190.  
  191. bool cross_seg_with_seg(point a, point b, point c, point d) {
  192. point pt;
  193. bool t = cross(line(a, b), line(c, d), pt);
  194. if (t == 0) return 0;
  195. return insight_seg(a, b, pt) && insight_seg(c, d, pt);
  196. }
  197.  
  198. ld dist_seg_to_seg(point a, point b, point c, point d) {
  199. if (a == b && c == d) return (a - c).len();
  200. if (a == b) return dist_to_seg(c, d, a);
  201. if (c == d) return dist_to_seg(a, b, c);
  202. if (cross_seg_with_seg(a, b, c, d)) return 0;
  203. return min(min(dist_to_seg(a, b, c), dist_to_seg(a, b, d)), min(dist_to_seg(c, d, a), dist_to_seg(c, d, b)));
  204. }
  205.  
  206. bool cross_seg_with_ray(point a, point b, point c, point d) {
  207. point pt;
  208. bool t = cross(line(a, b), line(c, d), pt);
  209. if (t == 0) return 0;
  210. return insight_seg(a, b, pt) && insight_ray(c, d, pt);
  211. }
  212.  
  213. ld dist_seg_to_ray(point a, point b, point c, point d) {
  214. if (a == b&& c == d) return (a - c).len();
  215. if (a == b) return dist_to_ray(c, d, a);
  216. if (c == d) return dist_to_ray(a, b, c);
  217. if (cross_seg_with_ray(a, b, c, d)) return 0;
  218. return min(min(dist_to_ray(c, d, a), dist_to_ray(c, d, b)), min(dist_to_seg(a, b, c), dist_to_seg(a, b, d)));
  219. }
  220.  
  221. bool cross_line_with_seg(point a, point b, line c) {
  222. point pt;
  223. bool t = cross(line(a, b), c, pt);
  224. if (!t) return 0;
  225. return insight_seg(a, b, pt);
  226. }
  227.  
  228. ld dist_seg_to_line(point a, point b, line c) {
  229. if (a == b && c.ff == c.ss) return (a - c.ff).len();
  230. if (a == b) return dist(c, a);
  231. if (c.ff == c.ss) return dist_to_seg(a, b, c.ff);
  232. if (cross_line_with_seg(a, b, c)) return 0;
  233. return min(dist(c, a), dist(c, b));
  234. }
  235.  
  236. bool cross_line_with_ray(point a, point b, line c) {
  237. point pt;
  238. bool t = cross(line(a, b), c, pt);
  239. if (!t) return 0;
  240. return insight_ray(a, b, pt);
  241. }
  242.  
  243. ld dist_ray_to_line(point a, point b, line c) {
  244. if (a == b && c.ff == c.ss) return (a - c.ff).len();
  245. if (a == b) return dist(c, a);
  246. if (c.ff == c.ss) return dist_to_ray(a, b, c.ff);
  247. if (cross_line_with_ray(a, b, c)) return 0;
  248. return min(dist(c, a), dist(c, b));
  249. }
  250.  
  251. bool cross_ray_with_ray(point a, point b, point c, point d) {
  252. point pt;
  253. bool t = cross(line(a, b), line(c, d), pt);
  254. if (t == 0) return 0;
  255. return insight_ray(a, b, pt) && insight_ray(c, d, pt);
  256. }
  257.  
  258. ld dist_ray_to_ray(point a, point b, point c, point d) {
  259. if (a == b && c == d) return (a - c).len();
  260. if (a == b) return dist_to_ray(c, d, a);
  261. if (c == d) return dist_to_ray(a, b, c);
  262. if (cross_ray_with_ray(a, b, c, d)) return 0;
  263. return min(min(dist_to_ray(a, b, c), dist_to_ray(a, b, d)), min(dist_to_ray(c, d, a), dist_to_ray(c, d, b)));
  264. }
  265.  
  266. int main() {
  267. ios::sync_with_stdio(false);
  268. cin.tie(0);
  269. #ifdef arrias
  270. freopen("true.txt", "r", stdin);
  271. #endif
  272.  
  273. cout.setf(ios::fixed);
  274. cout.precision(20);
  275.  
  276. point a, b, c, d;
  277. cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
  278.  
  279. /*set <pair<ld, ld>> st;
  280. st.insert({a.x, a.y});
  281. st.insert({b.x, b.y});
  282. st.insert({c.x, c.y});
  283. st.insert({d.x, d.y});
  284. assert(st.size() == 4);
  285.  
  286. */
  287. cout << (a - c).len() << "\n";
  288. cout << dist_to_seg(c, d, a) << "\n";
  289. cout << dist_to_ray(c, d, a) << "\n";
  290. cout << dist(line(c, d), a) << "\n";
  291.  
  292. cout << dist_to_seg(a, b, c) << "\n";
  293. cout << dist_seg_to_seg(a, b, c, d) << "\n";
  294. cout << dist_seg_to_ray(a, b, c, d) << "\n";
  295. cout << dist_seg_to_line(a, b, line(c, d)) << "\n";
  296.  
  297. cout << dist_to_ray(a, b, c) << "\n";
  298. cout << dist_seg_to_ray(c, d, a, b) << "\n";
  299. cout << dist_ray_to_ray(a, b, c, d) << "\n";
  300. cout << dist_ray_to_line(a, b, line(c, d)) << "\n";
  301.  
  302. cout << dist(line(a, b), c) << "\n";
  303. cout << dist_seg_to_line(c, d, line(a, b)) << "\n";
  304. cout << dist_ray_to_line(c, d, line(a, b)) << "\n";
  305. cout << dist(line(a, b), line(c, d)) << "\n";
  306.  
  307. return 0;
  308. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement