yeputons

Untitled

Mar 22nd, 2012
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.70 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cassert>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <string>
  8. #include <vector>
  9. #include <queue>
  10. #include <list>
  11. #include <set>
  12. #include <map>
  13.  
  14. using namespace std;
  15.  
  16. #define eprintf(...) fprintf(stderr, __ VA_ARGS__)
  17. #define pb push_back
  18. #define mp make_pair
  19. #define sz(x) ((int)(x).size())
  20. #define TASKNAME "segments"
  21.  
  22. typedef long long ll;
  23. typedef vector<ll> vll;
  24. typedef vector<int> vi;
  25. typedef vector<vi> vvi;
  26. typedef vector<bool> vb;
  27. typedef vector<vb> vvb;
  28. typedef pair<int, int> pii;
  29.  
  30. #define EPS 1e-8
  31. struct pt {
  32.   double x, y;
  33.   pt(double _x = 0, double _y = 0) : x(_x), y(_y) {}
  34.  
  35.   bool operator<(const pt &p2) const {
  36.     if (fabs(x - p2.x) < EPS) return x < p2.x;
  37.     return y < p2.y - EPS;
  38.   }
  39.   bool operator==(const pt &p2) const { return fabs(x - p2.x) < EPS && fabs(y - p2.y) < EPS; }
  40. };
  41. struct line {
  42.   double a, b, c;
  43.   line(const pt &p1, const pt &p2) {
  44.     a = p1.y - p2.y;
  45.     b = p2.x - p1.x;
  46.     c = -a * p1.x - b * p1.y;
  47.   }
  48.   bool cont(const pt &p) const { return fabs(a * p.x + b * p.y + c) < EPS; }
  49.  
  50.   pt operator&(const line &l2) {
  51.     double d = a * l2.b - b * l2.a;
  52.     if (fabs(d) < EPS) {
  53.       if (fabs(a * l2.c - c * l2.a) < EPS && fabs(b * l2.c - c * l2.b) < EPS)
  54.         throw 1;
  55.       else
  56.         throw 0;
  57.     }
  58.  
  59.     pt res(
  60.       (b * l2.c - c * l2.b) / d,
  61.       (a * l2.c - c * l2.a) / -d
  62.     );
  63.     assert(cont(res) && l2.cont(res));
  64.     return res;
  65.   }
  66. };
  67.  
  68. bool is_in(double x1, double x2, double x) {
  69.   if (x1 > x2) swap(x1, x2);
  70.   return x1 - EPS <= x && x <= x2 + EPS;
  71. }
  72. bool is_in(const pt &a, const pt &b, const pt &p) {
  73.   return is_in(a.x, b.x, p.x) && is_in(a.y, b.y, p.y);
  74. }
  75.  
  76. int main() {
  77.   freopen(TASKNAME ".in", "r", stdin);
  78.   freopen(TASKNAME ".out", "w", stdout);
  79.  
  80.   pt a1, a2, b1, b2;
  81.   while (scanf("%lf%lf", &a1.x, &a1.y) >= 1) {
  82.     scanf("%lf%lf", &a2.x, &a2.y);
  83.     scanf("%lf%lf", &b1.x, &b1.y);
  84.     scanf("%lf%lf", &b2.x, &b2.y);
  85.  
  86.     line l1(a1, a2), l2(b1, b2);
  87.  
  88.     vector<pt> res;
  89.     try {
  90.       res.pb(l1 & l2);
  91.     } catch (int cnt) {
  92.       eprintf("cnt=%d\n", cnt);
  93.       if (cnt > 0) {
  94.         res.pb(a1);
  95.         res.pb(a2);
  96.         res.pb(b1);
  97.         res.pb(b2);
  98.       }
  99.     }
  100.     sort(res.begin(), res.end());
  101.     res.resize(unique(res.begin(), res.end()) - res.begin());
  102.  
  103.     vector<pt> res2;
  104.     for (int i = 0; i < sz(res); i++) if (is_in(a1, a2, res[i]) && is_in(b1, b2, res[i]))
  105.       res2.pb(res[i]);
  106.     assert(sz(res2) <= 2);
  107.  
  108.     if (!sz(res2)) printf("Empty\n");
  109.     else
  110.       for (int i = 0; i < sz(res2); i++)
  111.         printf("%.18e %.18e\n", res2[i].x, res2[i].y);
  112.     break;
  113.   }
  114.   return 0;
  115. }
Add Comment
Please, Sign In to add comment