Advertisement
Guest User

Untitled

a guest
Feb 25th, 2020
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.38 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define REP(i, n) for(int i = 0; i < n; i++)
  5. #define FOR(i, a, b) for(int i = a; i <= b; i++)
  6. #define ST first
  7. #define ND second
  8.  
  9. ostream& operator<<(ostream &out, string str) {
  10.     for(char c : str) out << c;
  11.     return out;
  12. }
  13.  
  14. template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
  15.     return out << "(" << p.ST << ", " << p.ND << ")";
  16. }
  17.  
  18. template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
  19.     out << "{";
  20.     for(auto it = a.begin(); it != a.end(); it = next(it))
  21.         out << (it != a.begin() ? ", " : "") << *it;
  22.     return out << "}";
  23. }
  24.  
  25. void dump() { cerr << "\n"; }
  26. template<class T, class... Ts> void dump(T a, Ts... x) {
  27.     cerr << a << ", ";
  28.     dump(x...);
  29. }
  30.  
  31. #ifdef DEBUG
  32. #  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
  33. #else
  34. #  define debug(...) false
  35. #endif
  36.  
  37. template<class T> int size(T && a) { return a.size(); }
  38.  
  39. using LL = long long;
  40. using PII = pair<int, int>;
  41.  
  42. int sign(LL x) {
  43.     if(x < 0) return -1;
  44.     if(x > 0) return +1;
  45.     return 0;
  46. }
  47.  
  48. LL cross(PII a, PII b) {
  49.     return (LL) a.ST * b.ND - a.ND * b.ST;
  50. }
  51.  
  52. PII operator-(PII a, PII b) {
  53.     return {a.ST - b.ST, a.ND - b.ND};
  54. }
  55.  
  56. int side(PII a, PII b, PII p) {
  57.     return sign(cross(b - a, p - a));
  58. }
  59.  
  60. vector<int> rep;
  61. int find(int x) {
  62.     return rep[x] == x ? x : rep[x] = find(rep[x]);
  63. }
  64. bool join(int x, int y) {
  65.     x = find(x), y = find(y);
  66.     if(x == y) return false;
  67.     rep[x] = y;
  68.     return true;
  69. }
  70.  
  71. double dst(PII a, PII b) {
  72.     LL x = a.ST - b.ST, y = a.ND - b.ND;
  73.     return sqrt(x * x + y * y);
  74. }
  75.  
  76. int main() {
  77.     ios_base::sync_with_stdio(0);
  78.     cin.tie(0);
  79.  
  80.     int n;
  81.     cin >> n;
  82.  
  83.     vector<PII> p(n), q(n);
  84.     REP(i, n) cin >> p[i].ST >> p[i].ND >> q[i].ST >> q[i].ND;
  85.  
  86.     rep.resize(n);
  87.     REP(i, n) rep[i] = i;
  88.  
  89.     int edges = 0, comps = n;
  90.     REP(i, n) {
  91.         REP(j, i) {
  92.             bool a = side(p[i], q[i], p[j]) != side(p[i], q[i], q[j]);
  93.             bool b = side(p[j], q[j], p[i]) != side(p[j], q[j], q[i]);
  94.             bool good = a && b;
  95.             if(side(p[i], q[i], p[j]) == 0 && !a) {
  96.                 double max_dst = 0;
  97.                 for(auto &x : {p[i], q[i]})
  98.                     for(auto &y : {p[j], q[j]})
  99.                         max_dst = max(max_dst, dst(x, y));
  100.                 if(max_dst <= dst(p[i], q[i]) + dst(p[j], q[j]) + 1e-9)
  101.                     good = true;
  102.             }
  103.             if(good) {
  104.                 edges++;
  105.                 comps -= join(i, j);
  106.             }
  107.         }
  108.     }
  109.  
  110.     cout << edges - n + comps + 1 << "\n";
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement