Advertisement
Guest User

Untitled

a guest
Nov 20th, 2017
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(x) x.begin(), x.end()
  4. #define rall(x) x.rbegin(), x.rend()
  5. #define F first
  6. #define S second
  7. #define pb push_back
  8. #define ll long long
  9. #define ld long double
  10. #define double long double
  11.  
  12. using namespace std;
  13.  
  14. const double EPS = 1e-12;
  15. const double INF = 1e9;
  16.  
  17.  
  18. struct point;
  19. struct line;
  20. struct Vector;
  21.  
  22. vector<point> p;
  23.  
  24. //-----------POINT---------------
  25.  
  26. struct point {
  27.     double x, y;
  28.    
  29.     point(double a, double b) : x(a), y(b) {};
  30.     point() {};
  31. };
  32.  
  33. istream& operator>>(istream &is, point &dt)
  34. {
  35.     is >> dt.x >> dt.y;
  36.     return is;
  37. }
  38.  
  39. ostream &operator<<(ostream &is, point &dt)
  40. {
  41.     is << dt.x << " " << dt.y;
  42.     return is;
  43. }
  44.  
  45. bool operator==(point &a, point &b) {
  46.     if (a.x == b.x && a.y == b.y) return 1;
  47.     return 0;
  48. }
  49.  
  50. //-----------VECTOR---------------
  51.  
  52. struct Vector {
  53.     double x, y;
  54.    
  55.     Vector operator+(Vector & other) {
  56.         return {x + other.x, y + other.y};
  57.     }
  58.    
  59.     Vector operator/(double a) {
  60.         return {x / a, y / a};
  61.     }
  62.    
  63.     Vector operator*(double a) {
  64.         return {x * a, y * a};
  65.     }
  66.    
  67.     double length() {
  68.         return sqrt(x * x + y * y);
  69.     }
  70.    
  71.     void normal() {
  72.         double len = length();
  73.         x = x / len;
  74.         y = y / len;
  75.     }
  76.    
  77.     Vector(const point p1, const point p2) : x(p2.x - p1.x), y(p2.y - p1.y) {};
  78.     Vector(double x, double y) : x(x), y(y) {};
  79. };
  80.  
  81. point operator+(Vector a, point b) {
  82.     b.x += a.x;
  83.     b.y += a.y;
  84.     return b;
  85. }
  86.  
  87. //-----------LINE---------------
  88.  
  89. struct line {
  90.     double a, b, c;
  91.    
  92.     line(point x1, point x2) : a(x2.y - x1.y), b(x1.x - x2.x), c(-a * x1.x - b * x1.y) {};
  93. };
  94.  
  95. ostream& operator<<(ostream &is, line &dt)
  96. {
  97.     is << dt.a << " " << dt.b << " " << dt.c;
  98.     return is;
  99. }
  100.  
  101. //-----------SOLVE---------------
  102.  
  103. double scalar(Vector a, Vector b) {
  104.     return (a.x * b.x + a.y * b.y);
  105. }
  106.  
  107. double Pscalar(Vector a, Vector b) {
  108.     return (a.x * b.y - a.y * b.x);
  109. }
  110.  
  111. point lineIntersection(line line1, line line2) {
  112.     double x, y;
  113.     double a, b;
  114.     a = (line1.c * line2.b - line2.c * line1.b);
  115.     b = (line1.a * line2.b - line2.a * line1.b);
  116.     x = -(a / b);
  117.     a = (line1.a * line2.c - line2.a * line1.c);
  118.     b = (line1.a * line2.b - line2.a * line1.b);
  119.     y = -(a / b);
  120.     return {x, y};
  121. }
  122.  
  123. double distLine(point p, line a) {
  124.     double ans = 0;
  125.     ans = fabs(((a.a * p.x) + (a.b * p.y) + a.c) / (sqrt(a.a * a.a + a.b * a.b)));
  126.     return ans;
  127. }
  128.  
  129. bool OnLine(point p, line l) {
  130.     if (l.a * p.x + l.b * p.y + l.c == 0) {
  131.         return 1;
  132.     }
  133.     return 0;
  134. }
  135.  
  136. bool pointOnSegment(point p, point s, point t) {
  137.     line l(s, t);
  138.     if (OnLine(p, l) && scalar(Vector(s, p), Vector(t, p)) <= 0) {
  139.         return 1;
  140.     }
  141.     return 0;
  142. }
  143.  
  144. bool checkSegments(point s1, point t1, point s2, point t2) {
  145.     if (pointOnSegment(s1, s2, t2) || pointOnSegment(t1, s2, t2) || pointOnSegment(s2, s1, t1) || pointOnSegment(t2, s1, t1)) return 1;
  146.     Vector A(s1, t1);
  147.     Vector B(s2, t2);
  148.     if ((Pscalar(A, Vector(t1, s2)) * Pscalar(A, Vector(t1, t2)) < 0) &&
  149.         (Pscalar(B, Vector(t2, t1)) * Pscalar(B, Vector(t2, s1)) < 0)) {
  150.         return 1;
  151.     }
  152.     return 0;
  153. }
  154.  
  155. bool sidePolygon(int n, point s) {
  156.     point t(s.x + INF + 5, s.y + 1);
  157.     int cnt = 0;
  158.     for (int i = 0; i < n - 1; i++) {
  159.         if (checkSegments(s, t, p[i], p[i + 1])) cnt++;
  160.     }
  161.     if (checkSegments(s, t, p[n - 1], p[0])) cnt++;
  162.     if (cnt % 2 == 0) {
  163.         return 0;
  164.     } else {
  165.         return 1;
  166.     }
  167. }
  168.  
  169. void print_ans(point a, point b) {
  170.     if (a == b) {
  171.         cout << a.x << " " << a.y << "\n";
  172.         exit(0);
  173.     }
  174.     if (a.x == b.x) {
  175.         if (a.y < b.y) {
  176.             cout << a.x << " " << a.y << "\n";
  177.             cout << b.x << " " << b.y << "\n";
  178.             exit(0);
  179.         } else {
  180.             cout << b.x << " " << b.y << "\n";
  181.             cout << a.x << " " << a.y << "\n";
  182.             exit(0);
  183.         }
  184.     }
  185.     if (a.x > b.x) {
  186.         cout << b.x << " " << b.y << "\n";
  187.         cout << a.x << " " << a.y << "\n";
  188.         exit(0);
  189.     }
  190.     cout << a.x << " " << a.y << "\n";
  191.     cout << b.x << " " << b.y << "\n";
  192.     exit(0);
  193. }
  194.  
  195. bool cmp(point a, point b) {
  196.     pair<double, double> c1 = {a.x, a.y};
  197.     pair<double, double> c2 = {b.x, b.y};
  198.     return c1 < c2;
  199. }
  200.  
  201. int main() {
  202.     freopen("segments.in", "r", stdin);
  203.     freopen("segments.out", "w", stdout);
  204.     cout << fixed;
  205.     cout.precision(10);
  206.     point a, b, c, d;
  207.     cin >> a >> b >> c >> d;
  208.    
  209.     if ((a == c && b == d) || ((a == d) && (b == c))) {
  210.         print_ans(a, b);
  211.         return 0;
  212.     }
  213.    
  214.     line c1(a, b);
  215.     line c2(c, d);
  216.    
  217.     bool On1Line = Pscalar(Vector(a, b), Vector(c, d)) == 0 || Pscalar(Vector(a, b), Vector(d, c)) == 0;
  218.     if (!On1Line && !checkSegments(a, b, c, d)) {
  219.         cout << "Empty\n";
  220.         return 0;
  221.     }
  222.    
  223.     if (!On1Line && checkSegments(a, b, c, d)) {
  224.         point ans = lineIntersection(c1, c2);
  225.         cout << ans.x << " " << ans.y << '\n';
  226.         return 0;
  227.     } else { //c1 == c2
  228.         vector<point> ans;
  229.         if (pointOnSegment(a, c, d)) {
  230.             ans.pb(a);
  231.         }
  232.         if (pointOnSegment(b, c, d)) {
  233.             ans.pb(b);
  234.         }
  235.         if (pointOnSegment(c, a, b)) {
  236.             ans.pb(c);
  237.         }
  238.         if (pointOnSegment(d, a, b)) {
  239.             ans.pb(d);
  240.         }
  241.         if (ans.empty()) {
  242.             cout << "Empty\n";
  243.             return 0;
  244.         }
  245.         sort(all(ans), cmp);
  246.         if (ans.size() == 1) {
  247.             cout << ans[0].x << " " << ans[0].y << '\n';
  248.             return 0;
  249.         }
  250.         print_ans(ans[0], ans[ans.size() - 1]);
  251.         return 0;
  252.     }
  253. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement