Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define fi first
- #define se second
- #define pb push_back
- #define all(a) a.begin(), a.end()
- #define sz(a) (int)a.size()
- #define PI 3.14159265
- typedef long double ld;
- typedef long long ll;
- const ld EPS = 1e-6;
- const int MX = 2e5 + 1;
- const ld INF = 7e18;
- bitset<MX> b;
- struct point {
- ld x, y;
- point() {};
- point(ld x, ld y) {
- this -> x = x,
- this -> y = y;
- }
- point(const point& a) {
- x = a.x,
- y = a.y;
- }
- };
- point p[3];
- struct event {
- ld x;
- int type;
- int id;
- event() {};
- event(ld x, int type, int id) {
- this -> x = x,
- this -> type = type,
- this -> id = id;
- }
- };
- deque<event> a;
- point rot(point a, ld alpha) {
- alpha *= PI / 180.0;
- return point(a.x * cos(alpha) - a.y * sin(alpha), a.x * sin(alpha) + a.y * cos(alpha));
- }
- ld get(point a, point b) {
- if (a.x == b.x) return 90.0;
- if (a.y == b.y) return 0.0;
- if (a.y < b.y) swap(a, b);
- ld sign = 1;
- if (b.x < a.x) sign = -1.0;
- ld k1 = a.y - b.y, k2 = (b.x - a.x) * sign, h = hypot(k2, k1);
- ld r = acos(k2 / h) * 180.0 / PI;
- if (sign > 0) return min(r, 180.0 - r);
- return max(r, 180.0 - r);
- }
- bool check(ld alpha) {
- point pt[3];
- for (int i = 0; i < 3; ++i)
- pt[i] = rot(p[i], alpha);
- //for (int i = 0; i < 3; ++i) cout << pt[i].x << " " << pt[i].y << endl;
- return (pt[0].y - pt[1].y <= EPS && pt[0].y - pt[2].y <= EPS);
- }
- ld rot(ld alpha) {
- if (alpha <= 180.0)
- return alpha + 180.0;
- return alpha - 180.0;
- }
- void solve(deque<ld>& d, int time) {
- ld l = INF, r = -INF;
- int it = 0;
- for (int i = 0; i < 4; ++i) {
- l = INF, r = -INF;
- while (it < sz(d) && check(d[it]) == 0) ++it;
- if (it == sz(d)) return;
- l = d[it];
- ++it;
- while (it < sz(d) && check(d[it]) && check((d[it - 1] + d[it]) / 2.0)) ++it;
- r = d[--it];
- a.pb(event(l, 0, time)), a.pb(event(r, 1, time));
- ++it;
- if (it == sz(d) - 1) return;
- }
- }
- void print(deque<event>& d) {
- for (auto &pt : d)
- cout << pt.x << " " << pt.type << " " << pt.id << endl;
- cout << endl;
- }
- bool cmp(event& a, event& b) {
- if (fabs(a.x - b.x) <= EPS)
- return a.type < b.type;
- return (a.x - b.x < EPS);
- }
- main() {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- int n;
- cin >> n;
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < 3; ++j)
- cin >> p[j].x >> p[j].y;
- deque<ld> t;
- ld fi1 = get(p[0], p[1]), fi2 = get(p[0], p[2]);
- t.pb(fi1), t.pb(fi2);
- t.pb(rot(fi1)), t.pb(rot(fi2));
- sort(all(t));
- if (t[0] != 0.0) t.push_front(0.0);
- if (t[sz(t) - 1] != 360.0) t.pb(360.0);
- //for (auto &pt : t) cout << pt << " "; cout << '\n';
- solve(t, i);
- }
- int ans = -1, cur = 0;
- sort(all(a), cmp);
- for (auto &pt : a)
- if (pt.type == 0 && b[pt.id] == 0)
- ans = max(ans, ++cur), b[pt.id] = 1;
- else if (pt.type == 1)
- --cur, b[pt.id] = 0;
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement