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 acos(-1)
- typedef long double ld;
- const ld EPS = 1e-7;
- const int MX = 3e5;
- const ld INF = 7e18;
- struct event {
- ld x;
- int type, id;
- event() {};
- event(ld x, int type, int id) {
- this -> x = x,
- this -> type = type,
- this -> id = id;
- }
- };
- bitset<MX> b;
- int x[3], y[3];
- vector<event> a;
- ld get(int x1, int y1, int x2, int y2) {
- if (x1 == x2) return 90.0;
- if (y1 == y2) return 180.0;
- if (y1 < y2) swap(x1, x2), swap(y1, y2);
- bool sign = (x2 > x1);
- ld k1 = abs(x1 - x2), k2 = abs(y1 - y2), h = hypot(k1, k2);
- ld res = acos(k1 / h) * 180 / PI;
- return (sign ? res : 180.0 - res);
- }
- ld check(ld f) {
- f = f / 180.0 * PI;
- ld xt[3], yt[3];
- for (int i = 0; i < 3; ++i)
- xt[i] = ld(x[i]) * cos(f) - ld(y[i]) * sin(f),
- yt[i] = ld(x[i]) * sin(f) + ld(y[i]) * cos(f);
- //for (int i = 0; i < 3; ++i) cout << xt[i] << " " << yt[i] << endl;
- return (yt[0] - yt[1] <= EPS && yt[0] - yt[2] <= EPS);
- }
- bool cmp2(ld a, ld b) {
- return a - b <= EPS;
- }
- void solve(int time) {
- vector<ld> t;
- if (check(0.0)) t.pb(0.0);
- ld f1 = get(x[0], y[0], x[1], y[1]),
- f2 = get(x[1], y[1], x[2], y[2]),
- f3 = get(x[2], y[2], x[0], y[0]);
- t.pb(f1), t.pb(f1 + 180.0);
- t.pb(f2), t.pb(f2 + 180.0);
- t.pb(f3), t.pb(f3 + 180.0);
- t.pb(360.0);
- sort(all(t), cmp2);
- //for (auto &pt : t) cout << pt << " " << check(pt) << endl;
- int l = -1, r, it = 0;
- while (it < sz(t)) {
- while (it < sz(t) && !check(t[it])) ++it;
- if (it == sz(t)) return;
- l = it;
- while (it < sz(t) && check(t[it])) ++it;
- r = it - 1;
- if (l == r) return;
- //cout << t[l] << " " << t[r] << endl;
- a.pb(event(t[l], 0, time)), a.pb(event(t[r], 1, time));
- }
- }
- 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 >> x[j] >> y[j];
- solve(i);
- }
- int ans = 1, cur = 0;
- sort(all(a), cmp);
- //for (auto &pt : a) cout << pt.x << " " << pt.type << " " << pt.id << endl;
- 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)
- ans = max(ans, --cur), b[pt.id] = 0;
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement