Advertisement
MrHitch

Untitled

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