fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define MP make_pair
  6. #define PB push_back
  7. #define LL long long
  8. #define int LL
  9. #define VI vector<int>
  10. #define LD long double
  11. #define PII pair<int,int>
  12. #define ALL(x) (x).begin(), (x).end()
  13. #define SZ(x) ((int)(x).size())
  14. #define FOR(i,a,b) for (int i = (a); i <= (b); i++)
  15. #define REP(i,n) FOR(i,0,(int)(n)-1)
  16. #define RE(i,n) FOR(i,1,n)
  17. #define R(i,n) REP(i,n)
  18. #define FI first
  19. #define SE second
  20. #define st FI
  21. #define nd SE
  22.  
  23. template<class C> void mini(C&a4, C b4) { a4 = min(a4, b4); }
  24. template<class C> void maxi(C&a4, C b4) { a4 = max(a4, b4); }
  25.  
  26. template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
  27. template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  28.   while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<","; _dbg(sdbg+1, a...);
  29. }
  30.  
  31. template<class T> ostream &operator<<(ostream &os, vector<T> V) {
  32.   os << "["; for (auto vv : V) os << vv << ","; return os << "]";
  33. }
  34.  
  35. #ifdef LOCAL
  36. #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
  37. #else
  38. #define debug(...) (__VA_ARGS__)
  39. #define cerr if(0)cout
  40. #endif
  41.  
  42. LD Sq(LD x) {
  43.   return x * x;
  44. }
  45.  
  46. const LD kEps = 1e-9;
  47. struct Point {
  48.   LD x, y;
  49.   Point operator-(Point p) { return {x - p.x, y - p.y}; }
  50.   Point operator+(Point p) { return {x + p.x, y + p.y}; }
  51.   Point operator*(LD f) { return {x * f, y * f}; }
  52.   bool operator<(const Point& A) const {
  53.     if (abs(A.x - x) > kEps) { return x < A.x; }
  54.     return y < A.y;
  55.   }
  56.   friend ostream& operator<<(ostream& out, Point p) {
  57.     return out<<"("<<p.x<<", "<<p.y<<")";
  58.   }
  59. };
  60.  
  61. LD Dist(Point A, Point B) {
  62.   return sqrt(Sq(A.x - B.x) + Sq(A.y - B.y));
  63. }
  64.  
  65. LD CrossProd(Point A, Point B) {
  66.   return A.x * B.y - A.y * B.x;
  67. }
  68.  
  69. LD CrossProd(Point A, Point B, Point C) {
  70.   B = B - A;
  71.   C = C - A;
  72.   return CrossProd(B, C);
  73. }
  74.  
  75. struct Line {
  76.   Point p[2];
  77.   Point& operator[](int a) {
  78.     return p[a];
  79.   }
  80. };
  81.  
  82.  
  83.  
  84. vector<Point> InterLineLine(Point A, Point B, Point P, Point Q) {
  85.   LD tr_area = CrossProd(A, P, Q);
  86.   LD quad_area = CrossProd(A, P, B) + CrossProd(A, B, Q);
  87.   if (abs(quad_area) < kEps) {
  88.     return {};
  89.   }
  90.   return {A + (B - A) * (tr_area / quad_area)};
  91. } 
  92.  
  93. const int N = 222;
  94. Point pts[N];
  95.  
  96. bool PtOnLine(Point A, Line l) {
  97.   return abs(CrossProd(l[0], A, l[1])) < kEps;
  98. }
  99.  
  100. bool PtOnSeg(Point A, Point P, Point Q) {
  101.   return abs(Dist(P, Q) - Dist(A, P) - Dist(A, Q)) < kEps;
  102. }
  103.  
  104. int32_t main() {
  105.   ios_base::sync_with_stdio(0);
  106.   cin.tie(0);
  107.   cout << fixed << setprecision(11);
  108.   cerr << fixed << setprecision(6);
  109.  
  110.  
  111.   int n;
  112.   cin>>n;
  113.   RE (i, n) {
  114.     int x, y;
  115.     cin>>x>>y;
  116.     pts[i] = {(LD)x, (LD)y};
  117.   }
  118.   pts[n + 1] = pts[1];
  119.   pts[n + 2] = pts[2];
  120.   LD area = 0;
  121.   RE (ii, n) {
  122.     area += CrossProd(pts[ii], pts[ii + 1]);
  123.   }
  124.   if (area < 0) {
  125.     reverse(pts + 1, pts + n + 3);
  126.   }
  127.   debug(pts[1], pts[2]);
  128.   LD res = 0;
  129.   RE (ii, n) {
  130.     RE (jj, ii - 1) {
  131.       Line l = {pts[ii], pts[jj]};
  132.       vector<Point> inters;
  133.       RE (k, n) {
  134.         bool b1 = PtOnLine(pts[k], l),
  135.              b2 = PtOnLine(pts[k + 1], l),
  136.              b3 = PtOnLine(pts[k + 2], l);
  137.         if (!b2 && !b1) {
  138.           vector<Point> hehs = InterLineLine(pts[ii], pts[jj], pts[k], pts[k + 1]);
  139.           if (hehs.empty()) { continue; }
  140.           if (PtOnSeg(hehs[0], pts[k], pts[k + 1])) {
  141.             inters.PB(hehs[0]);
  142.           }
  143.         } else if (b1 && !b2) {
  144.         } else if (b1 || b3) {
  145.           if (CrossProd(pts[k], pts[k + 1], pts[k + 2]) > 0) {
  146.             inters.PB(pts[k + 1]);
  147.           }
  148.         } else {
  149.           if ((CrossProd(l[1] - l[0], pts[k + 1] - pts[k]) > 0) == (CrossProd(l[1] - l[0], pts[k + 2] - pts[k + 1]) > 0)) {
  150.             inters.PB(pts[k + 1]);
  151.           }
  152.         }
  153.       }
  154.       sort(ALL(inters));
  155.       debug(inters);
  156.       if (SZ(inters) % 2) {
  157.         debug(pts[ii], pts[jj]);
  158.       }
  159.       assert(SZ(inters) % 2 == 0);
  160.       for (int i = 0; i < SZ(inters); i += 2) {
  161.         maxi(res, Dist(inters[i], inters[i + 1]));
  162.       }
  163.     }
  164.   }
  165.  
  166.   cout<<res<<endl;
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194. }
  195.  
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
7
0 20
40 0
40 20
70 50
50 70
30 50
0 50
stdout
copy 
76.15773105864
https://ideone.com/08pisZ
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!