Advertisement
Guest User

Untitled

a guest
May 24th, 2017
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <string>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <set>
  9. #include <map>
  10. #include <cmath>
  11. #include <ctime>
  12. #include <functional>
  13. #include <sstream>
  14. #include <fstream>
  15. #include <valarray>
  16. #include <complex>
  17. #include <queue>
  18. #include <cassert>
  19. #include <bitset>
  20. using namespace std;
  21.  
  22. #ifdef LOCAL
  23.     #define debug_flag 0
  24. #else
  25.     #define debug_flag 0
  26. #endif
  27.  
  28. template <class T1, class T2 >
  29. std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p)
  30. {
  31.     os << "[" << p.first << ", " << p.second << "]";
  32.     return os;
  33. }
  34.  
  35. template <class T >
  36. std::ostream& operator << (std::ostream& os, const std::vector<T>& v)
  37. {
  38.     os << "[";
  39.     bool first = true;
  40.     for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
  41.     {
  42.         if (!first)
  43.             os << ", ";
  44.         first = false;
  45.         os << *it;
  46.     }
  47.     os << "]";
  48.     return os;
  49. }
  50.  
  51. #define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }
  52.  
  53. vector<string> _split(const string& s, char c) {
  54.     vector<string> v;
  55.     stringstream ss(s);
  56.     string x;
  57.     while (getline(ss, x, c))
  58.         v.emplace_back(x);
  59.     return v;
  60. }
  61.  
  62. void _print(vector<string>::iterator) {}
  63. template<typename T, typename... Args>
  64. void _print(vector<string>::iterator it, T a, Args... args) {
  65.     string name = it -> substr((*it)[0] == ' ', it -> length());
  66.     if (isalpha(name[0]))
  67.         cerr << name  << " = " << a << " ";
  68.     else
  69.         cerr << name << " ";
  70.     _print(++it, args...);
  71. }
  72.  
  73. typedef long long int int64;
  74. typedef long double ldouble;
  75.  
  76. const ldouble EPS = 1e-9;
  77. const ldouble ldouble_INF = 1e18;
  78.  
  79. bool eq(ldouble a, ldouble b)
  80. {
  81.     return fabsl(a - b) < EPS;
  82. }
  83.  
  84. bool ls(ldouble a, ldouble b)
  85. {
  86.     return a < b && !eq(a, b);
  87. }
  88.  
  89. bool gr(ldouble a, ldouble b)
  90. {
  91.     return a > b && !eq(a, b);
  92. }
  93.  
  94. bool ls_eq(ldouble a, ldouble b)
  95. {
  96.     return a < b || eq(a, b);
  97. }
  98.  
  99. bool gr_eq(ldouble a, ldouble b)
  100. {
  101.     return a > b || eq(a, b);
  102. }
  103.  
  104. ldouble safe_sqrt(ldouble a)
  105. {
  106.     assert(gr_eq(a, 0));
  107.     if (a < 0)
  108.         return 0;
  109.     return sqrtl(a);
  110. }
  111.  
  112. ldouble next_double()
  113. {
  114.     double a;
  115.     scanf("%lf", &a);
  116.     return a;
  117. }
  118.  
  119. struct Point
  120. {
  121.     ldouble x, y;
  122.  
  123.     Point() : x(), y() {}
  124.     Point(ldouble _x, ldouble _y) : x(_x), y(_y) {}
  125.  
  126.     void scan()
  127.     {
  128.         x = next_double();
  129.         y = next_double();
  130.     }
  131.  
  132.     bool is_zero() const
  133.     {
  134.         return eq(x, 0) && eq(y, 0);
  135.     }
  136.  
  137.     Point operator + (const Point &p) const
  138.     {
  139.         return Point(x + p.x, y + p.y);
  140.     }
  141.  
  142.     Point operator - (const Point &p) const
  143.     {
  144.         return Point(x - p.x, y - p.y);
  145.     }
  146.  
  147.     Point operator * (const ldouble &k) const
  148.     {
  149.         return Point(x * k, y * k);
  150.     }
  151.  
  152.     Point operator / (const ldouble &k) const
  153.     {
  154.         return Point(x / k, y / k);
  155.     }
  156.  
  157.     ldouble operator % (const Point &p) const
  158.     {
  159.         return x * p.x + y * p.y;
  160.     }
  161.  
  162.     ldouble length() const
  163.     {
  164.         return safe_sqrt(*this % *this);
  165.     }
  166.  
  167.     ldouble dist_to(const Point &p) const
  168.     {
  169.         return (*this - p).length();
  170.     }
  171.  
  172.     ldouble operator * (const Point &p) const
  173.     {
  174.         return x * p.y - y * p.x;
  175.     }
  176.  
  177.     bool on_line(const Point &A, const Point &B) const
  178.     {
  179.         return eq((A - *this) * (B - *this), 0);
  180.     }
  181.  
  182.     bool on_seg(const Point &A, const Point &B) const
  183.     {
  184.         return on_line(A, B) &&
  185.             ls_eq((A - *this) % (B - *this), 0);
  186.     }
  187.  
  188.     Point normalize(ldouble k)
  189.     {
  190.         return *this / length() * k;
  191.     }
  192. };
  193.  
  194. std::ostream& operator << (std::ostream& os, const Point &p)
  195. {
  196.     os << "(" << p.x << ", " << p.y << ")";
  197.     return os;
  198. }
  199.  
  200. bool intersect_lines(const Point &A, const Point &B, const Point &C, const Point &D, Point &M)
  201. {
  202.     ldouble s1 = (C - A) * (D - A);
  203.     ldouble s2 = (D - B) * (C - B);
  204.     ldouble s = s1 + s2;
  205.     if (eq(s, 0))
  206.         return false;
  207.     M = A + (B - A) / s * s1;
  208.     return true;
  209. }
  210.  
  211. void fix_order(vector<Point> & points)
  212. {
  213.     int n = (int)points.size();
  214.    
  215.     ldouble mul = 0;
  216.     for (int i = 0; i < n; i++)
  217.     {
  218.         Point A = points[i];
  219.         Point B = points[(i + 1) % n];
  220.         mul += A * B;
  221.     }
  222.  
  223.     if (ls(mul, 0))
  224.         reverse(points.begin(), points.end());
  225. }
  226.  
  227. bool is_inside_polygon(const Point & P, const vector<Point> & points)
  228. {
  229.     int n = (int)points.size();
  230.  
  231.     for (int i = 0; i < n; i++)
  232.         if (P.on_seg(points[i], points[(i + 1) % n]))
  233.             return true;
  234.  
  235.     int cnt = 0;
  236.  
  237.     for (int i = 0; i < n; i++)
  238.     {
  239.         Point A = points[i];
  240.         Point B = points[(i + 1) % n];
  241.  
  242.         A = A - P;
  243.         B = B - P;
  244.  
  245.         if (ls(A.y, B.y))
  246.             swap(A, B);
  247.  
  248.         if (gr_eq(A.y, 0) && gr_eq(B.y, 0))
  249.             continue;
  250.  
  251.         if (ls(A.y, 0) && ls(B.y, 0))
  252.             continue;
  253.  
  254.         ldouble mul = A * B;
  255.  
  256.         assert(!eq(mul, 0));
  257.  
  258.         if (ls(mul, 0))
  259.             cnt++;
  260.     }
  261.  
  262.     return cnt % 2 == 1;
  263. }
  264.  
  265. bool segs_are_intersect(ldouble l1, ldouble r1, ldouble l2, ldouble r2)
  266. {
  267.     if (l1 > r1)
  268.         swap(l1, r1);
  269.     if (l2 > r2)
  270.         swap(l2, r2);
  271.     ldouble l = max(l1, l2);
  272.     ldouble r = min(r1, r2);
  273.     return ls_eq(l, r);
  274. }
  275.  
  276. int get_sign(ldouble a)
  277. {
  278.     if (ls(a, 0))
  279.         return -1;
  280.     if (eq(a, 0))
  281.         return 0;
  282.     return 1;
  283. }
  284.  
  285. bool segs_are_intersect(const Point &A, const Point &B, const Point &C, const Point &D)
  286. {
  287.     if (!segs_are_intersect(A.x, B.x, C.x, D.x))
  288.         return false;
  289.    
  290.     if (!segs_are_intersect(A.y, B.y, C.y, D.y))
  291.         return false;
  292.  
  293.     return get_sign((B - A) * (C - A)) * get_sign((B - A) * (D - A)) <= 0 &&
  294.         get_sign((D - C) * (A - C)) * get_sign((D - C) * (B - C)) <= 0;
  295. }
  296.  
  297. bool pred(Point a, Point b)
  298. {
  299.     if (eq(a * b, 0))
  300.         return gr(a % b, 0);
  301.     return gr(a * b, 0);
  302. }
  303.  
  304. bool is_between(Point c, Point a, Point b)
  305. {
  306.     if (c.is_zero())
  307.         return true;
  308.  
  309.     if (pred(a, b))
  310.         return pred(a, c) && pred(c, b);
  311.     return pred(a, c) || pred(c, b);
  312. }
  313.  
  314. ldouble solve(const Point & P1, const Point & P2, const vector<Point> & points)
  315. {
  316.     //check that [P1, P2] is inside polygon. if yes return the length of maximum intersection
  317.  
  318.     //dbg("solve", P1, P2, points);
  319.  
  320.     Point MID = (P1 + P2) / 2;
  321.  
  322.     if (!is_inside_polygon(MID, points))
  323.         return 0;
  324.  
  325.     int n = (int)points.size();
  326.  
  327.     for (int i = 0; i < n; i++)
  328.     {
  329.         Point A = points[i];
  330.         Point B = points[(i + 1) % n];
  331.  
  332.         if (A.on_line(P1, P2) && B.on_line(P1, P2))
  333.             continue;
  334.  
  335.         if (P1.on_seg(A, B) || P2.on_seg(A, B))
  336.             continue;
  337.  
  338.         if (B.on_seg(P1, P2))
  339.         {
  340.             Point C = points[(i + 2) % n];
  341.             if (!is_between(P1 - B, C - B, A - B))
  342.                 return 0;
  343.             if (!is_between(P2 - B, C - B, A - B))
  344.                 return 0;
  345.             continue;
  346.         }
  347.  
  348.         if (A.on_seg(P1, P2))
  349.         {
  350.             Point C = points[(i + n - 1) % n];
  351.             if (!is_between(P1 - A, B - A, C - A))
  352.                 return 0;
  353.             if (!is_between(P2 - A, B - A, C - A))
  354.                 return 0;
  355.             continue;
  356.         }
  357.  
  358.         if (segs_are_intersect(A, B, P1, P2))
  359.             return 0;
  360.     }
  361.  
  362.     Point v = (P2 - P1).normalize(1);
  363.  
  364.     Point P1_INF = P1 - v.normalize(3000);
  365.     Point P2_INF = P1 + v.normalize(3000);
  366.  
  367.     //dbg(P1_INF, P2_INF);
  368.  
  369.     ldouble len = P1.dist_to(P2);
  370.  
  371.     ldouble min_x = -ldouble_INF;
  372.     ldouble max_x = ldouble_INF;
  373.  
  374.     for (int i = 0; i < n; i++)
  375.     {
  376.         Point A = points[i];
  377.         Point B = points[(i + 1) % n];
  378.  
  379.         if (A.on_line(P1, P2) && B.on_line(P1, P2))
  380.             continue;
  381.  
  382.         if (B.on_seg(P1_INF, P2_INF))
  383.         {
  384.             Point C = points[(i + 2) % n];
  385.             if (!is_between(P1_INF - B, C - B, A - B) || !is_between(P2_INF - B, C - B, A - B))
  386.             {
  387.                 ldouble x = (B - P1) % v;
  388.                 if (gr_eq(x, len))
  389.                     max_x = min(max_x, x);
  390.                 else
  391.                     min_x = max(min_x, x);
  392.             }
  393.             continue;
  394.         }
  395.  
  396.         if (A.on_seg(P1_INF, P2_INF))
  397.         {
  398.             Point C = points[(i + n - 1) % n];
  399.             //dbg(A, B, C);
  400.             if (!is_between(P1_INF - A, B - A, C - A) || !is_between(P2_INF - A, B - A, C - A))
  401.             {
  402.                 ldouble x = (A - P1) % v;
  403.                 if (gr_eq(x, len))
  404.                     max_x = min(max_x, x);
  405.                 else
  406.                     min_x = max(min_x, x);
  407.             }
  408.             continue;
  409.         }
  410.  
  411.         Point M;
  412.         if (intersect_lines(A, B, P1, P2, M))
  413.         {
  414.             if (!M.on_seg(A, B))
  415.                 continue;
  416.             ldouble x = (M - P1) % v;
  417.             if (gr_eq(x, len))
  418.                 max_x = min(max_x, x);
  419.             else
  420.                 min_x = max(min_x, x);
  421.         }
  422.     }
  423.  
  424.     return max_x - min_x;
  425. }
  426.  
  427. int main()
  428. {
  429. #ifdef LOCAL
  430.     freopen ("input.txt", "r", stdin);
  431. #endif
  432.  
  433.     int n;
  434.     scanf("%d", &n);
  435.     vector<Point> points(n);
  436.     for (int i = 0; i < n; i++)
  437.         points[i].scan();
  438.  
  439.     fix_order(points);
  440.  
  441.     ldouble ans = 0;
  442.  
  443.     //dbg(solve(points[0], points[1], points));
  444.     //return 0;
  445.  
  446.     for (int i = 0; i < n; i++)
  447.     {
  448.         for (int j = i + 1; j < n; j++)
  449.         {
  450.             ldouble cur_ans = solve(points[i], points[j], points);
  451.             dbg(i, j, cur_ans);
  452.             ans = max(ans, cur_ans);
  453.         }
  454.     }
  455.  
  456.     printf("%.10lf\n", (double)ans);
  457.  
  458.     return 0;
  459. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement