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;
- typedef long long ll;
- const ld EPS = 1e-7;
- const int MX = 3e5;
- 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 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 = 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 r;
- return 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 <= EPS)
- return alpha + 180.0;
- return alpha - 180.0;
- }
- ld mid(ld a, ld b) {
- return (a + b) / 2.0;
- }
- ld bin(ld a, ld b) {
- ld l = a, r = b, m;
- for (int i = 0; i < 20; ++i) {
- m = mid(l, r);
- if (check(m))
- l = m;
- else
- r = m;
- }
- return mid(l, r);
- }
- void solve(ld alpha, int time) {
- ld beta = rot(alpha), ans;
- if (beta - alpha <= EPS) swap(alpha, beta);
- if (check(alpha)) {
- ans = bin(alpha, beta);
- a.pb(event(alpha, 0, time)), a.pb(event(ans, 1, time));
- }
- else {
- ans = bin(beta, alpha + 360.0);
- //cout << alpha << " " << beta << " " << time << " ";
- //cout << ans << " * \n";
- if (ans >= 360) {
- ans -= 360;
- if (beta - ans <= EPS) swap(beta, ans);
- a.pb(event(beta, 0, time)), a.pb(event(360, 1, time));
- a.pb(event(0, 0, time)), a.pb(event(ans, 1, time));
- }
- else {
- if (ans - beta <= EPS) swap(beta, ans);
- a.pb(event(beta, 0, time)), a.pb(event(ans, 1, time));
- }
- }
- }
- 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;
- solve(get(p[0], p[1]), i);
- solve(get(p[0], p[2]), i);
- }
- //print(a);
- int ans = -1, cur = 0;
- sort(all(a), cmp);
- //print(a);
- 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