Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <cmath>
- #include <ctime>
- #include <functional>
- #include <sstream>
- #include <fstream>
- #include <valarray>
- #include <complex>
- #include <queue>
- #include <cassert>
- #include <bitset>
- using namespace std;
- #ifdef LOCAL
- #define debug_flag 0
- #else
- #define debug_flag 0
- #endif
- template <class T1, class T2 >
- std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p)
- {
- os << "[" << p.first << ", " << p.second << "]";
- return os;
- }
- template <class T >
- std::ostream& operator << (std::ostream& os, const std::vector<T>& v)
- {
- os << "[";
- bool first = true;
- for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
- {
- if (!first)
- os << ", ";
- first = false;
- os << *it;
- }
- os << "]";
- return os;
- }
- #define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }
- vector<string> _split(const string& s, char c) {
- vector<string> v;
- stringstream ss(s);
- string x;
- while (getline(ss, x, c))
- v.emplace_back(x);
- return v;
- }
- void _print(vector<string>::iterator) {}
- template<typename T, typename... Args>
- void _print(vector<string>::iterator it, T a, Args... args) {
- string name = it -> substr((*it)[0] == ' ', it -> length());
- if (isalpha(name[0]))
- cerr << name << " = " << a << " ";
- else
- cerr << name << " ";
- _print(++it, args...);
- }
- typedef long long int int64;
- typedef long double ldouble;
- const ldouble EPS = 1e-9;
- const ldouble ldouble_INF = 1e18;
- bool eq(ldouble a, ldouble b)
- {
- return fabsl(a - b) < EPS;
- }
- bool ls(ldouble a, ldouble b)
- {
- return a < b && !eq(a, b);
- }
- bool gr(ldouble a, ldouble b)
- {
- return a > b && !eq(a, b);
- }
- bool ls_eq(ldouble a, ldouble b)
- {
- return a < b || eq(a, b);
- }
- bool gr_eq(ldouble a, ldouble b)
- {
- return a > b || eq(a, b);
- }
- ldouble safe_sqrt(ldouble a)
- {
- assert(gr_eq(a, 0));
- if (a < 0)
- return 0;
- return sqrtl(a);
- }
- ldouble next_double()
- {
- double a;
- scanf("%lf", &a);
- return a;
- }
- struct Point
- {
- ldouble x, y;
- Point() : x(), y() {}
- Point(ldouble _x, ldouble _y) : x(_x), y(_y) {}
- void scan()
- {
- x = next_double();
- y = next_double();
- }
- bool is_zero() const
- {
- return eq(x, 0) && eq(y, 0);
- }
- Point operator + (const Point &p) const
- {
- return Point(x + p.x, y + p.y);
- }
- Point operator - (const Point &p) const
- {
- return Point(x - p.x, y - p.y);
- }
- Point operator * (const ldouble &k) const
- {
- return Point(x * k, y * k);
- }
- Point operator / (const ldouble &k) const
- {
- return Point(x / k, y / k);
- }
- ldouble operator % (const Point &p) const
- {
- return x * p.x + y * p.y;
- }
- ldouble length() const
- {
- return safe_sqrt(*this % *this);
- }
- ldouble dist_to(const Point &p) const
- {
- return (*this - p).length();
- }
- ldouble operator * (const Point &p) const
- {
- return x * p.y - y * p.x;
- }
- bool on_line(const Point &A, const Point &B) const
- {
- return eq((A - *this) * (B - *this), 0);
- }
- bool on_seg(const Point &A, const Point &B) const
- {
- return on_line(A, B) &&
- ls_eq((A - *this) % (B - *this), 0);
- }
- Point normalize(ldouble k)
- {
- return *this / length() * k;
- }
- };
- std::ostream& operator << (std::ostream& os, const Point &p)
- {
- os << "(" << p.x << ", " << p.y << ")";
- return os;
- }
- bool intersect_lines(const Point &A, const Point &B, const Point &C, const Point &D, Point &M)
- {
- ldouble s1 = (C - A) * (D - A);
- ldouble s2 = (D - B) * (C - B);
- ldouble s = s1 + s2;
- if (eq(s, 0))
- return false;
- M = A + (B - A) / s * s1;
- return true;
- }
- void fix_order(vector<Point> & points)
- {
- int n = (int)points.size();
- ldouble mul = 0;
- for (int i = 0; i < n; i++)
- {
- Point A = points[i];
- Point B = points[(i + 1) % n];
- mul += A * B;
- }
- if (ls(mul, 0))
- reverse(points.begin(), points.end());
- }
- bool is_inside_polygon(const Point & P, const vector<Point> & points)
- {
- int n = (int)points.size();
- for (int i = 0; i < n; i++)
- if (P.on_seg(points[i], points[(i + 1) % n]))
- return true;
- int cnt = 0;
- for (int i = 0; i < n; i++)
- {
- Point A = points[i];
- Point B = points[(i + 1) % n];
- A = A - P;
- B = B - P;
- if (ls(A.y, B.y))
- swap(A, B);
- if (gr_eq(A.y, 0) && gr_eq(B.y, 0))
- continue;
- if (ls(A.y, 0) && ls(B.y, 0))
- continue;
- ldouble mul = A * B;
- assert(!eq(mul, 0));
- if (ls(mul, 0))
- cnt++;
- }
- return cnt % 2 == 1;
- }
- bool segs_are_intersect(ldouble l1, ldouble r1, ldouble l2, ldouble r2)
- {
- if (l1 > r1)
- swap(l1, r1);
- if (l2 > r2)
- swap(l2, r2);
- ldouble l = max(l1, l2);
- ldouble r = min(r1, r2);
- return ls_eq(l, r);
- }
- int get_sign(ldouble a)
- {
- if (ls(a, 0))
- return -1;
- if (eq(a, 0))
- return 0;
- return 1;
- }
- bool segs_are_intersect(const Point &A, const Point &B, const Point &C, const Point &D)
- {
- if (!segs_are_intersect(A.x, B.x, C.x, D.x))
- return false;
- if (!segs_are_intersect(A.y, B.y, C.y, D.y))
- return false;
- return get_sign((B - A) * (C - A)) * get_sign((B - A) * (D - A)) <= 0 &&
- get_sign((D - C) * (A - C)) * get_sign((D - C) * (B - C)) <= 0;
- }
- bool pred(Point a, Point b)
- {
- if (eq(a * b, 0))
- return gr(a % b, 0);
- return gr(a * b, 0);
- }
- bool is_between(Point c, Point a, Point b)
- {
- if (c.is_zero())
- return true;
- if (pred(a, b))
- return pred(a, c) && pred(c, b);
- return pred(a, c) || pred(c, b);
- }
- ldouble solve(const Point & P1, const Point & P2, const vector<Point> & points)
- {
- //check that [P1, P2] is inside polygon. if yes return the length of maximum intersection
- //dbg("solve", P1, P2, points);
- Point MID = (P1 + P2) / 2;
- if (!is_inside_polygon(MID, points))
- return 0;
- int n = (int)points.size();
- for (int i = 0; i < n; i++)
- {
- Point A = points[i];
- Point B = points[(i + 1) % n];
- if (A.on_line(P1, P2) && B.on_line(P1, P2))
- continue;
- if (P1.on_seg(A, B) || P2.on_seg(A, B))
- continue;
- if (B.on_seg(P1, P2))
- {
- Point C = points[(i + 2) % n];
- if (!is_between(P1 - B, C - B, A - B))
- return 0;
- if (!is_between(P2 - B, C - B, A - B))
- return 0;
- continue;
- }
- if (A.on_seg(P1, P2))
- {
- Point C = points[(i + n - 1) % n];
- if (!is_between(P1 - A, B - A, C - A))
- return 0;
- if (!is_between(P2 - A, B - A, C - A))
- return 0;
- continue;
- }
- if (segs_are_intersect(A, B, P1, P2))
- return 0;
- }
- Point v = (P2 - P1).normalize(1);
- Point P1_INF = P1 - v.normalize(3000);
- Point P2_INF = P1 + v.normalize(3000);
- //dbg(P1_INF, P2_INF);
- ldouble len = P1.dist_to(P2);
- ldouble min_x = -ldouble_INF;
- ldouble max_x = ldouble_INF;
- for (int i = 0; i < n; i++)
- {
- Point A = points[i];
- Point B = points[(i + 1) % n];
- if (A.on_line(P1, P2) && B.on_line(P1, P2))
- continue;
- if (B.on_seg(P1_INF, P2_INF))
- {
- Point C = points[(i + 2) % n];
- if (!is_between(P1_INF - B, C - B, A - B) || !is_between(P2_INF - B, C - B, A - B))
- {
- ldouble x = (B - P1) % v;
- if (gr_eq(x, len))
- max_x = min(max_x, x);
- else
- min_x = max(min_x, x);
- }
- continue;
- }
- if (A.on_seg(P1_INF, P2_INF))
- {
- Point C = points[(i + n - 1) % n];
- //dbg(A, B, C);
- if (!is_between(P1_INF - A, B - A, C - A) || !is_between(P2_INF - A, B - A, C - A))
- {
- ldouble x = (A - P1) % v;
- if (gr_eq(x, len))
- max_x = min(max_x, x);
- else
- min_x = max(min_x, x);
- }
- continue;
- }
- Point M;
- if (intersect_lines(A, B, P1, P2, M))
- {
- if (!M.on_seg(A, B))
- continue;
- ldouble x = (M - P1) % v;
- if (gr_eq(x, len))
- max_x = min(max_x, x);
- else
- min_x = max(min_x, x);
- }
- }
- return max_x - min_x;
- }
- int main()
- {
- #ifdef LOCAL
- freopen ("input.txt", "r", stdin);
- #endif
- int n;
- scanf("%d", &n);
- vector<Point> points(n);
- for (int i = 0; i < n; i++)
- points[i].scan();
- fix_order(points);
- ldouble ans = 0;
- //dbg(solve(points[0], points[1], points));
- //return 0;
- for (int i = 0; i < n; i++)
- {
- for (int j = i + 1; j < n; j++)
- {
- ldouble cur_ans = solve(points[i], points[j], points);
- dbg(i, j, cur_ans);
- ans = max(ans, cur_ans);
- }
- }
- printf("%.10lf\n", (double)ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement