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-8;
- const int MX = 2e5 + 1;
- const ld INF = 7e18;
- ld x[4], y[4];
- bitset<MX> b;
- 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;
- ld get(ld x1, ld y1, ld x2, ld y2) {
- ld sign = 1.0;
- if (y1 < y2) swap(x1, x2), swap(y1, y2);
- if (x2 < x1) sign = -1.0;
- ld k1 = y1 - y2, k2 = (x2 - x1) * sign;
- if (k1 == 0.0) return 0;
- if (k2 == 0.0) return 90.0;
- ld h = hypot(k1, k2);
- ld r = acos(k2 / h) * 180.0 / PI;
- if (sign > 0) return r;
- return 180.0 - r;
- }
- bool check(ld fi) {
- fi = fi * PI / 180.0;
- ld yt[4], t1 = sin(fi), t2 = cos(fi);
- for (int i = 1; i < 4; ++i)
- yt[i] = x[i] * t1 + y[i] * t2;
- return (yt[1] - yt[2] <= EPS && yt[1] - yt[3] <= EPS);
- }
- bool cmp(event& a, event& b) {
- return (a.x - b.x < EPS || (abs(a.x - b.x) <= EPS && a.type < b.type));
- }
- main() {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- int n;
- cin >> n;
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j < 4; ++j) cin >> x[j] >> y[j];
- ld f1 = get(x[1], y[1], x[2], y[2]), f2 = get(x[1], y[1], x[3], y[3]);
- ld f3 = (180.0 - f1 <= EPS ? f1 - 180.0 : f1 + 180.0), f4 = (180.0 - f2 <= EPS ? f2 - 180.0 : f2 + 180.0);
- deque<ld> t;
- t.pb(f1), t.pb(f2), t.pb(f3), t.pb(f4);
- sort(all(t));
- t.push_front(0.0), t.push_back(360.0);
- ld l = INF, r = -INF;
- for (int j = 0; j < sz(t) - 1; ++j) {
- if (check(t[j]) && check(t[j + 1]) && check((t[j] + t[j + 1]) / 2.0))
- l = min(t[j], l), r = max(t[j + 1], r);
- else if (l != INF && r != -INF) {
- a.pb(event(l, 0, i)), a.pb(event(r, 1, i));
- l = INF, r = -INF;
- }
- }
- }
- sort(all(a), cmp);
- int ans = 1, cur = 0;
- for (auto &pt : a) {
- if (pt.type == 0 && b[pt.id] == 0) ans = max(ans, ++cur), b[pt.id] = 1;
- if (pt.type == 1) b[pt.id] = 0, --cur;
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement