Advertisement
MrHitch

Untitled

Jan 8th, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.45 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.  
  15. const ld EPS = 1e-7;
  16. const int MX = 3e5;
  17. const ld INF = 7e18;
  18.  
  19. struct event {
  20.     ld x;
  21.     int type, id;
  22.     event() {};
  23.     event(ld x, int type, int id) {
  24.         this -> x = x,
  25.         this -> type = type,
  26.         this -> id = id;
  27.     }
  28. };
  29.  
  30. bitset<MX> b;
  31.  
  32. int x[3], y[3];
  33.  
  34. vector<event> a;
  35.  
  36. ld get(int x1, int y1, int x2, int y2) {
  37.     if (x1 == x2) return 90.0;
  38.     if (y1 == y2) return 180.0;
  39.     if (y1 < y2) swap(x1, x2), swap(y1, y2);
  40.     bool sign = (x2 > x1);
  41.     ld k1 = abs(x1 - x2), k2 = abs(y1 - y2), h = hypot(k1, k2);
  42.     ld res = acos(k1 / h) * 180 / PI;
  43.     return (sign ? res : 180.0 - res);
  44. }
  45.  
  46. ld check(ld f) {
  47.     f = f / 180.0 * PI;
  48.     ld xt[3], yt[3];
  49.     for (int i = 0; i < 3; ++i)
  50.         xt[i] = ld(x[i]) * cos(f) - ld(y[i]) * sin(f),
  51.         yt[i] = ld(x[i]) * sin(f) + ld(y[i]) * cos(f);
  52.     //for (int i = 0; i < 3; ++i) cout << xt[i] << " " << yt[i] << endl;
  53.     return (yt[0] - yt[1] <= EPS && yt[0] - yt[2] <= EPS);
  54. }
  55.  
  56. bool cmp2(ld a, ld b) {
  57.     return a - b <= EPS;
  58. }
  59.  
  60. void solve(int time) {
  61.     vector<ld> t;
  62.     if (check(0.0)) t.pb(0.0);
  63.     ld f1 = get(x[0], y[0], x[1], y[1]),
  64.         f2 = get(x[1], y[1], x[2], y[2]),
  65.         f3 = get(x[2], y[2], x[0], y[0]);
  66.     t.pb(f1), t.pb(f1 + 180.0);
  67.     t.pb(f2), t.pb(f2 + 180.0);
  68.     t.pb(f3), t.pb(f3 + 180.0);
  69.     t.pb(360.0);
  70.     sort(all(t), cmp2);
  71.     //for (auto &pt : t) cout << pt << " " << check(pt) << endl;
  72.     int l = -1, r, it = 0;
  73.     while (it < sz(t)) {
  74.         while (it < sz(t) && !check(t[it])) ++it;
  75.         if (it == sz(t)) return;
  76.         l = it;
  77.         while (it < sz(t) && check(t[it])) ++it;
  78.         r = it - 1;
  79.         if (l == r) return;
  80.         //cout << t[l] << " " << t[r] << endl;
  81.         a.pb(event(t[l], 0, time)), a.pb(event(t[r], 1, time));
  82.     }
  83. }
  84.  
  85. bool cmp(event a, event b) {
  86.     if (fabs(a.x - b.x) <= EPS)
  87.         return a.type < b.type;
  88.     return a.x - b.x < EPS;
  89. }
  90.  
  91. main() {
  92.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  93.     int n;
  94.     cin >> n;
  95.     for (int i = 0; i < n; ++i) {
  96.         for (int j = 0; j < 3; ++j)
  97.             cin >> x[j] >> y[j];
  98.         solve(i);
  99.     }
  100.     int ans = 1, cur = 0;
  101.     sort(all(a), cmp);
  102.     //for (auto &pt : a) cout << pt.x << " " << pt.type << " " << pt.id << endl;
  103.     for (auto &pt : a)
  104.         if (pt.type == 0 && b[pt.id] == 0)
  105.             ans = max(ans, ++cur), b[pt.id] = 1;
  106.         else if (pt.type == 1) 
  107.             ans = max(ans, --cur), b[pt.id] = 0;
  108.     cout << ans;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement