Advertisement
Guest User

Untitled

a guest
Apr 21st, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct vect
  6. {
  7.     long long x, y;
  8.     vect(long long x, long long y) : x(x), y(y) {}
  9.     long long operator *(vect a)
  10.     {
  11.         if (x * a.y - y * a.x == 0) return 0;
  12.         return (x * a.y - y * a.x) / abs(x * a.y - y * a.x);
  13.     }
  14.     vect operator -(vect a)
  15.     {
  16.         return vect(x - a.x, y - a.y);
  17.     }
  18. };
  19.  
  20. struct seg
  21. {
  22.     long long x1, y1, x2, y2;
  23.     seg(long long x1, long long y1, long long x2, long long y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
  24. };
  25.  
  26. bool intersect(seg ab, seg cd)
  27. {
  28.     vect a1 = vect(ab.x2, ab.y2) - vect(ab.x1, ab.y1);
  29.     vect ac = vect(cd.x1, cd.y1) - vect(ab.x1, ab.y1);
  30.     vect ad = vect(cd.x2, cd.y2) - vect(ab.x1, ab.y1);
  31.     vect c1 = vect(cd.x2, cd.y2) - vect(cd.x1, cd.y1);
  32.     vect ca = vect(ab.x1, ab.y1) - vect(cd.x1, cd.y1);
  33.     vect cb = vect(ab.x2, ab.y2) - vect(cd.x1, cd.y1);
  34.     return (c1 * ca) * (c1 * cb) <= 0 && (a1 * ac) * (a1 * ad) <= 0;
  35. }
  36. vector<int> a[250];
  37. vector<int> mt;
  38. vector<char> used;
  39.  
  40. bool try_kuhn (int v) {
  41.     if (used[v])  return false;
  42.     used[v] = true;
  43.     for (size_t i=0; i<a[v].size(); ++i) {
  44.         int to = a[v][i];
  45.         if (mt[to] == -1 || try_kuhn (mt[to])) {
  46.             mt[to] = v;
  47.             return true;
  48.         }
  49.     }
  50.     return false;
  51. }
  52.  
  53.  
  54. int main()
  55. {
  56.     int n;
  57.     cin >> n;
  58.     vector<seg> v;
  59.     for (int i = 0; i < n; i++)
  60.     {
  61.         long long x1, y1, x2, y2;
  62.         cin >> x1 >> y1 >> x2 >> y2;
  63.         v.push_back(seg(x1, y1, x2, y2));
  64.     }
  65.     for (int i = 0; i < n; i++)
  66.     {
  67.         for (int j = 0; j < n; j++)
  68.         {
  69.             if (j == i) continue;
  70.             if (intersect(v[i], v[j]))
  71.             {
  72.                 a[i].push_back(j);
  73.             }
  74.         }
  75.     }
  76.     mt.assign (n, -1);
  77.     for (int i = 0; i < n; ++i) {
  78.         if (v[i].x1 == v[i].x2)
  79.         {
  80.             used.assign (n, false);
  81.             try_kuhn (i);
  82.         }
  83.  
  84.     }
  85.  
  86.     int ans = 0;
  87.     for (int i=0; i<n; ++i)
  88.         if (mt[i] != -1)
  89.             ans++;
  90.     cout << n - ans;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement