Advertisement
MrHitch

Untitled

Jan 7th, 2018
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.15 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define all(a) a.begin(), a.end()
  9. #define sz(a) (int)a.size()
  10.  
  11. #define PI 3.14159265
  12.  
  13. typedef long double ld;
  14. typedef long long ll;
  15.  
  16. const ld EPS = 1e-8;
  17. const int MX = 2e5 + 1;
  18. const ld INF = 7e18;
  19.  
  20. ld x[4], y[4];
  21.  
  22. bitset<MX> b;
  23.  
  24. struct event {
  25.     ld x;
  26.     int type;
  27.     int id;
  28.     event() {};
  29.     event(ld x, int type, int id) {
  30.         this -> x = x,
  31.         this -> type = type,
  32.         this -> id = id;
  33.     }
  34. };
  35.  
  36. deque<event> a;
  37.  
  38. ld get(ld x1, ld y1, ld x2, ld y2) {
  39.     ld sign = 1.0;
  40.     if (y1 < y2) swap(x1, x2), swap(y1, y2);
  41.     if (x2 < x1) sign = -1.0;
  42.     ld k1 = y1 - y2, k2 = (x2 - x1) * sign;
  43.     if (k1 == 0.0) return 0;
  44.     if (k2 == 0.0) return 90.0;
  45.     ld h = hypot(k1, k2);
  46.     ld r = acos(k2 / h) * 180.0 / PI;
  47.     if (sign > 0) return r;
  48.     return 180.0 - r;
  49. }
  50.  
  51. bool check(ld fi) {
  52.     fi = fi * PI / 180.0;
  53.     ld yt[4], t1 = sin(fi), t2 = cos(fi);
  54.     for (int i = 1; i < 4; ++i)
  55.         yt[i] = x[i] * t1 + y[i] * t2;
  56.     return (yt[1] - yt[2] <= EPS && yt[1] - yt[3] <= EPS);
  57. }
  58.  
  59. bool cmp(event& a, event& b) {
  60.     return (a.x - b.x < EPS || (abs(a.x - b.x) <= EPS && a.type < b.type));
  61. }  
  62.  
  63. main() {
  64.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  65.     int n;
  66.     cin >> n;
  67.     for (int i = 1; i <= n; ++i) {
  68.         for (int j = 1; j < 4; ++j) cin >> x[j] >> y[j];
  69.         ld f1 = get(x[1], y[1], x[2], y[2]), f2 = get(x[1], y[1], x[3], y[3]);
  70.         ld f3 = (180.0 - f1 <= EPS ? f1 - 180.0 : f1 + 180.0), f4 = (180.0 - f2 <= EPS ? f2 - 180.0 : f2 + 180.0);
  71.         deque<ld> t;
  72.         t.pb(f1), t.pb(f2), t.pb(f3), t.pb(f4);
  73.         sort(all(t));
  74.         t.push_front(0.0), t.push_back(360.0);
  75.         ld l = INF, r = -INF;
  76.         for (int j = 0; j < sz(t) - 1; ++j) {
  77.             if (check(t[j]) && check(t[j + 1]) && check((t[j] + t[j + 1]) / 2.0))
  78.                 l = min(t[j], l), r = max(t[j + 1], r);
  79.             else if (l != INF && r != -INF) {
  80.                 a.pb(event(l, 0, i)), a.pb(event(r, 1, i));
  81.                 l = INF, r = -INF;
  82.             }
  83.         }
  84.     }
  85.     sort(all(a), cmp);
  86.     int ans = 1, cur = 0;
  87.     for (auto &pt : a) {
  88.         if (pt.type == 0 && b[pt.id] == 0) ans = max(ans, ++cur), b[pt.id] = 1;
  89.         if (pt.type == 1) b[pt.id] = 0, --cur;
  90.     }
  91.     cout << ans;   
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement