Advertisement
Guest User

Untitled

a guest
May 24th, 2017
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.84 KB | None | 0 0
  1. #pragma GCC optimize("O3")
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include <fstream>
  4. #include <iostream>
  5. #include <string>
  6. #include <complex>
  7. #include <math.h>
  8. #include <set>
  9. #include <vector>
  10. #include <map>
  11. #include <queue>
  12. #include <stdio.h>
  13. #include <stack>
  14. #include <algorithm>
  15. #include <list>
  16. #include <ctime>
  17.  
  18. #include <memory.h>
  19. #include <assert.h>
  20.  
  21. #define y0 sdkfaslhagaklsldk
  22.  
  23. #define y1 aasdfasdfasdf
  24. #define yn askfhwqriuperikldjk
  25. #define j1 assdgsdgasghsf
  26. #define tm sdfjahlfasfh
  27. #define lr asgasgash
  28. #define norm asdfasdgasdgsd
  29. #define have adsgagshdshfhds
  30. #define ends asdgahhfdsfshdshfd
  31.  
  32. #define eps 1e-11
  33. #define M_PI 3.141592653589793
  34. #define bs 1000000007
  35. #define bsize 512
  36.  
  37. #define ldouble long double
  38.  
  39. using namespace std;
  40.  
  41. long long INF = 1e9;
  42. const int N = 531;
  43.  
  44. int n;
  45. struct pt
  46. {
  47.     double x;
  48.     double y;
  49. };
  50.  
  51. struct Line
  52. {
  53.     double a;
  54.     double b;
  55.     double c;
  56. };
  57.  
  58. pt mid_point(pt a,pt b)
  59. {
  60.     a.x+=b.x;
  61.     a.y+=b.y;
  62.     a.x/=2;
  63.     a.y/=2;
  64.     return a;
  65. }
  66.  
  67. double get_dist(pt a,pt b)
  68. {
  69.     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
  70. }
  71.  
  72. bool cmp(pt a,pt b)
  73. {
  74.     if (fabs(a.x-b.x)>eps)
  75.         return a.x<b.x;
  76.     return a.y<b.y;
  77. }
  78.  
  79. bool equal(pt a,pt b)
  80. {
  81.     return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;
  82. }
  83.  
  84. vector<pt> normalize(vector<pt> v){
  85.  
  86.     vector<pt> ret;
  87.     for (int i=0;i<v.size();i++)
  88.     {
  89.         int ok=1;
  90.         for (int j=0;j<ret.size();j++)
  91.         {
  92.             if (equal(ret[j],v[i]))
  93.                 ok=0;
  94.         }
  95.  
  96.         if (ok)
  97.             ret.push_back(v[i]);
  98.     }
  99.     return ret;
  100. }
  101.  
  102. double get_area(pt a,pt b,pt c)
  103. {
  104.     return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
  105. }
  106.  
  107. bool is_in(double val,double l,double r)
  108. {
  109.     return val>=min(l,r)-eps&&val<=max(l,r)+eps;
  110. }
  111.  
  112. bool lies_on(pt a,pt l,pt r)
  113. {
  114.     return is_in(a.x,l.x,r.x)&&is_in(a.y,l.y,r.y)&&((fabs(get_area(a,l,r))<1e-7));
  115. }
  116.  
  117. bool lies_strictly_on(pt a,pt l,pt r)
  118. {
  119.     if (equal(a,l)||equal(a,r))
  120.         return false;
  121.     return lies_on(a,l,r);
  122. }
  123.  
  124. Line get_line(pt a,pt b)
  125. {
  126.     Line ret;
  127.     ret.a=(b.y-a.y);
  128.     ret.b=(a.x-b.x);
  129.     ret.c=-(a.x*ret.a+a.y*ret.b);
  130.     return ret;
  131. }
  132.  
  133. double det(double a,double b,double c,double d)
  134. {
  135.     return a*d-b*c;
  136. }
  137.  
  138. bool intersect(Line n,Line m,pt &ret)
  139. {
  140.     double zn=det(m.a,m.b,n.a,n.b);
  141.     if (fabs(zn)<eps)
  142.         return false;
  143.     ret.x=-det(m.c,m.b,n.c,n.b)/zn;
  144.     ret.y=-det(m.a,m.c,n.a,n.c)/zn;
  145.     return true;
  146. }
  147.  
  148. pt p[N];
  149.  
  150. bool is_inside(pt temp)
  151. {
  152.     pt goal;
  153.     goal.x=temp.x+2081;
  154.     goal.y=temp.y+2083;
  155.     int cnt=0;
  156.     Line a=get_line(temp,goal);
  157.  
  158.     for (int i=0;i<n;i++)
  159.     {
  160.         if (lies_on(temp,p[i],p[(i+1)%n]))
  161.             return true;
  162.     }
  163.  
  164.     pt ip;
  165.     Line b;
  166.  
  167.     for (int i=0;i<n;i++)
  168.     {
  169.         b=get_line(p[i],p[(i+1)%n]);
  170.         if (!intersect(a,b,ip))
  171.             continue;
  172.         //cout<<ip.x<<" "<<ip.y<<" "<<fixed<<get_area(ip,temp,goal)<<endl;
  173.         if (lies_on(ip,p[i],p[(i+1)%n])&&lies_on(ip,temp,goal))
  174.         {
  175.             ++cnt;
  176.         //  cout<<ip.x<<"^"<<ip.y<<endl;
  177.         }
  178.     }
  179. //  cout<<temp.x<<" "<<temp.y<<" "<<cnt<<endl;
  180.     return (cnt%2);
  181. }
  182.  
  183. double ans;
  184.  
  185.  
  186.  
  187. int main(){
  188.     //freopen("tree.in","r",stdin);
  189.     //freopen("tree.out","w",stdout);
  190.     //freopen("in.txt", "r", stdin);
  191.     //freopen("out.txt", "w", stdout);
  192.     ios_base::sync_with_stdio(0);
  193.     //cin.tie(0);
  194.  
  195.     cin>>n;
  196.     for (int i=0;i<n;i++)
  197.     {
  198.         cin>>p[i].x>>p[i].y;
  199.     }
  200.  
  201.     ans=0;
  202.  
  203.     for (int i=0;i<n;i++)
  204.     {
  205.         for (int j=i+1;j<n;j++)
  206.         {
  207.             bool ok=1;
  208.             for (int q=0;q<n;q++)
  209.             {
  210.                 if (q!=i&&q!=j&&lies_on(p[q],p[i],p[j]))
  211.                 {
  212.                     //cout<<i<<" "<<j<<" "<<q<<endl;
  213.                     ok=0;
  214.                 }
  215.             }
  216.  
  217.             if (!ok)
  218.                 continue;
  219.  
  220.             //cout<<i<<"%"<<j<<endl;
  221.  
  222.             Line l1=get_line(p[i],p[j]);
  223.             for (int q=0;q<n;q++)
  224.             {
  225.                 Line l2=get_line(p[q],p[(q+1)%n]);
  226.                 pt temp;
  227.                 if (!intersect(l1,l2,temp))
  228.                     continue;
  229.                 if (!lies_on(temp,p[q],p[(q+1)%n]))
  230.                     continue;
  231.                 if (!lies_strictly_on(temp,p[i],p[j]))
  232.                     continue;
  233. //              cout<<temp.x<<" "<<temp.y<<" "<<i<<" "<<j<<endl;
  234.                 ok=0;
  235.                 break;
  236.             }
  237.  
  238.     //      cout<<i<<"^"<<j<<endl;
  239.             if (!ok)
  240.                 continue;
  241.  
  242.             vector<pt> pts_list;
  243.  
  244.             for (int q=0;q<n;q++)
  245.             {
  246.                 Line l2=get_line(p[q],p[(q+1)%n]);
  247.                 pt temp;
  248.                 if (!intersect(l1,l2,temp))
  249.                     continue;
  250.                 if (!lies_on(temp,p[q],p[(q+1)%n]))
  251.                     continue;
  252.                 pts_list.push_back(temp);
  253.             }
  254.             pts_list=normalize(pts_list);
  255.  
  256.             sort(pts_list.begin(),pts_list.end(),cmp);
  257.  
  258.             //cout<<i<<"%"<<j<<" "<<pts_list.size()<<endl;
  259.  
  260.             if (get_dist(pts_list[0],pts_list.back())<=ans+eps)
  261.                 continue;
  262.  
  263.             double cur_len=0;
  264.             for (int i=0;i+1<pts_list.size();i++)
  265.             {
  266.                 if (cur_len+get_dist(pts_list[i],pts_list.back())<=ans+eps)
  267.                     break;
  268.  
  269.                 pt mid=mid_point(pts_list[i],pts_list[i+1]);
  270.                 //cout<<mid.x<<" "<<mid.y<<endl;
  271.                 if (!is_inside(mid))
  272.                 {
  273.                     cur_len=0;
  274.                     continue;
  275.                 }
  276.                 cur_len+=get_dist(pts_list[i+1],pts_list[i]);
  277.                 ans=max(ans,cur_len);
  278.             }
  279.         }
  280.     }
  281.  
  282.     cout.precision(10);
  283.  
  284.     cout<<fixed<<ans<<endl;
  285.  
  286.     cin.get(); cin.get();
  287.     return 0;
  288. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement