Advertisement
MrHitch

Untitled

Jan 7th, 2018
406
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.85 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-6;
  17. const int MX = 2e5 + 1;
  18. const ld INF = 7e18;
  19.  
  20. bitset<MX> b;
  21.  
  22. struct point {
  23.     ld x, y;
  24.     point() {};
  25.     point(ld x, ld y) {
  26.         this -> x = x,
  27.         this -> y = y;
  28.     }
  29.     point(const point& a) {
  30.         x = a.x,
  31.         y = a.y;
  32.     }
  33. };
  34.  
  35. point p[3];
  36.  
  37. struct event {
  38.     ld x;
  39.     int type;
  40.     int id;
  41.     event() {};
  42.     event(ld x, int type, int id) {
  43.         this -> x = x,
  44.         this -> type = type,
  45.         this -> id = id;
  46.     }
  47. };
  48.  
  49. deque<event> a;
  50.  
  51. point rot(point a, ld alpha) {
  52.     alpha *= PI / 180.0;
  53.     return point(a.x * cos(alpha) - a.y * sin(alpha), a.x * sin(alpha) + a.y * cos(alpha));
  54. }
  55.  
  56. ld get(point a, point b) {
  57.     if (a.x == b.x) return 90.0;
  58.     if (a.y == b.y) return 0.0;
  59.     if (a.y < b.y) swap(a, b);
  60.     ld sign = 1;
  61.     if (b.x < a.x) sign = -1.0;
  62.     ld k1 = a.y - b.y, k2 = (b.x - a.x) * sign, h = hypot(k2, k1);
  63.     ld r = acos(k2 / h) * 180.0 / PI;
  64.     if (sign > 0) return min(r, 180.0 - r);
  65.     return max(r, 180.0 - r);
  66. }
  67.  
  68. bool check(ld alpha) {
  69.     point pt[3];
  70.     for (int i = 0; i < 3; ++i)
  71.         pt[i] = rot(p[i], alpha);
  72.     //for (int i = 0; i < 3; ++i) cout << pt[i].x << " " << pt[i].y << endl;
  73.     return (pt[0].y - pt[1].y <= EPS && pt[0].y - pt[2].y <= EPS);
  74. }
  75.  
  76. ld rot(ld alpha) {
  77.     if (alpha <= 180.0)
  78.         return alpha + 180.0;
  79.     return alpha - 180.0;
  80. }
  81.  
  82. void solve(deque<ld>& d, int time) {
  83.     ld l = INF, r = -INF;
  84.     int it = 0;
  85.     for (int i = 0; i < 4; ++i) {
  86.         l = INF, r = -INF;
  87.         while (it < sz(d) && check(d[it]) == 0) ++it;
  88.         if (it == sz(d)) return;
  89.         l = d[it];
  90.         ++it;
  91.         while (it < sz(d) && check(d[it]) && check((d[it - 1] + d[it]) / 2.0)) ++it;
  92.         r = d[--it];
  93.         a.pb(event(l, 0, time)), a.pb(event(r, 1, time));
  94.         ++it;
  95.         if (it == sz(d) - 1) return;
  96.     }
  97. }
  98.  
  99. void print(deque<event>& d) {
  100.     for (auto &pt : d)
  101.         cout << pt.x << " " << pt.type << " " << pt.id << endl;
  102.     cout << endl;
  103. }
  104.  
  105. bool cmp(event& a, event& b) {
  106.     if (fabs(a.x - b.x) <= EPS)
  107.         return a.type < b.type;
  108.     return (a.x - b.x < EPS);
  109. }
  110.  
  111. main() {
  112.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  113.     int n;
  114.     cin >> n;
  115.     for (int i = 0; i < n; ++i) {
  116.         for (int j = 0; j < 3; ++j)
  117.             cin >> p[j].x >> p[j].y;
  118.         deque<ld> t;
  119.         ld fi1 = get(p[0], p[1]), fi2 = get(p[0], p[2]);
  120.         t.pb(fi1), t.pb(fi2);
  121.         t.pb(rot(fi1)), t.pb(rot(fi2));
  122.         sort(all(t));
  123.         if (t[0] != 0.0) t.push_front(0.0);
  124.         if (t[sz(t) - 1] != 360.0) t.pb(360.0);
  125.         //for (auto &pt : t) cout << pt << " "; cout << '\n';
  126.         solve(t, i);
  127.     }
  128.     int ans = -1, cur = 0;
  129.     sort(all(a), cmp);
  130.     for (auto &pt : a)
  131.         if (pt.type == 0 && b[pt.id] == 0)
  132.             ans = max(ans, ++cur), b[pt.id] = 1;
  133.         else if (pt.type == 1)
  134.             --cur, b[pt.id] = 0;
  135.     cout << ans;
  136. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement