Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("O3")
- #define _CRT_SECURE_NO_WARNINGS
- #include <fstream>
- #include <iostream>
- #include <string>
- #include <complex>
- #include <math.h>
- #include <set>
- #include <vector>
- #include <map>
- #include <queue>
- #include <stdio.h>
- #include <stack>
- #include <algorithm>
- #include <list>
- #include <ctime>
- #include <memory.h>
- #include <assert.h>
- #define y0 sdkfaslhagaklsldk
- #define y1 aasdfasdfasdf
- #define yn askfhwqriuperikldjk
- #define j1 assdgsdgasghsf
- #define tm sdfjahlfasfh
- #define lr asgasgash
- #define norm asdfasdgasdgsd
- #define have adsgagshdshfhds
- #define ends asdgahhfdsfshdshfd
- #define eps 1e-11
- #define M_PI 3.141592653589793
- #define bs 1000000007
- #define bsize 512
- #define ldouble long double
- using namespace std;
- long long INF = 1e9;
- const int N = 531;
- int n;
- struct pt
- {
- double x;
- double y;
- };
- struct Line
- {
- double a;
- double b;
- double c;
- };
- pt mid_point(pt a,pt b)
- {
- a.x+=b.x;
- a.y+=b.y;
- a.x/=2;
- a.y/=2;
- return a;
- }
- double get_dist(pt a,pt b)
- {
- return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
- }
- bool cmp(pt a,pt b)
- {
- if (fabs(a.x-b.x)>eps)
- return a.x<b.x;
- return a.y<b.y;
- }
- bool equal(pt a,pt b)
- {
- return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;
- }
- vector<pt> normalize(vector<pt> v){
- vector<pt> ret;
- for (int i=0;i<v.size();i++)
- {
- int ok=1;
- for (int j=0;j<ret.size();j++)
- {
- if (equal(ret[j],v[i]))
- ok=0;
- }
- if (ok)
- ret.push_back(v[i]);
- }
- return ret;
- }
- double get_area(pt a,pt b,pt c)
- {
- return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
- }
- bool is_in(double val,double l,double r)
- {
- return val>=min(l,r)-eps&&val<=max(l,r)+eps;
- }
- bool lies_on(pt a,pt l,pt r)
- {
- 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));
- }
- bool lies_strictly_on(pt a,pt l,pt r)
- {
- if (equal(a,l)||equal(a,r))
- return false;
- return lies_on(a,l,r);
- }
- Line get_line(pt a,pt b)
- {
- Line ret;
- ret.a=(b.y-a.y);
- ret.b=(a.x-b.x);
- ret.c=-(a.x*ret.a+a.y*ret.b);
- return ret;
- }
- double det(double a,double b,double c,double d)
- {
- return a*d-b*c;
- }
- bool intersect(Line n,Line m,pt &ret)
- {
- double zn=det(m.a,m.b,n.a,n.b);
- if (fabs(zn)<eps)
- return false;
- ret.x=-det(m.c,m.b,n.c,n.b)/zn;
- ret.y=-det(m.a,m.c,n.a,n.c)/zn;
- return true;
- }
- pt p[N];
- bool is_inside(pt temp)
- {
- pt goal;
- goal.x=temp.x+2081;
- goal.y=temp.y+2083;
- int cnt=0;
- Line a=get_line(temp,goal);
- for (int i=0;i<n;i++)
- {
- if (lies_on(temp,p[i],p[(i+1)%n]))
- return true;
- }
- pt ip;
- Line b;
- for (int i=0;i<n;i++)
- {
- b=get_line(p[i],p[(i+1)%n]);
- if (!intersect(a,b,ip))
- continue;
- //cout<<ip.x<<" "<<ip.y<<" "<<fixed<<get_area(ip,temp,goal)<<endl;
- if (lies_on(ip,p[i],p[(i+1)%n])&&lies_on(ip,temp,goal))
- {
- ++cnt;
- // cout<<ip.x<<"^"<<ip.y<<endl;
- }
- }
- // cout<<temp.x<<" "<<temp.y<<" "<<cnt<<endl;
- return (cnt%2);
- }
- double ans;
- int main(){
- //freopen("tree.in","r",stdin);
- //freopen("tree.out","w",stdout);
- //freopen("in.txt", "r", stdin);
- //freopen("out.txt", "w", stdout);
- ios_base::sync_with_stdio(0);
- //cin.tie(0);
- cin>>n;
- for (int i=0;i<n;i++)
- {
- cin>>p[i].x>>p[i].y;
- }
- ans=0;
- for (int i=0;i<n;i++)
- {
- for (int j=i+1;j<n;j++)
- {
- bool ok=1;
- for (int q=0;q<n;q++)
- {
- if (q!=i&&q!=j&&lies_on(p[q],p[i],p[j]))
- {
- //cout<<i<<" "<<j<<" "<<q<<endl;
- ok=0;
- }
- }
- if (!ok)
- continue;
- //cout<<i<<"%"<<j<<endl;
- Line l1=get_line(p[i],p[j]);
- for (int q=0;q<n;q++)
- {
- Line l2=get_line(p[q],p[(q+1)%n]);
- pt temp;
- if (!intersect(l1,l2,temp))
- continue;
- if (!lies_on(temp,p[q],p[(q+1)%n]))
- continue;
- if (!lies_strictly_on(temp,p[i],p[j]))
- continue;
- // cout<<temp.x<<" "<<temp.y<<" "<<i<<" "<<j<<endl;
- ok=0;
- break;
- }
- // cout<<i<<"^"<<j<<endl;
- if (!ok)
- continue;
- vector<pt> pts_list;
- for (int q=0;q<n;q++)
- {
- Line l2=get_line(p[q],p[(q+1)%n]);
- pt temp;
- if (!intersect(l1,l2,temp))
- continue;
- if (!lies_on(temp,p[q],p[(q+1)%n]))
- continue;
- pts_list.push_back(temp);
- }
- pts_list=normalize(pts_list);
- sort(pts_list.begin(),pts_list.end(),cmp);
- //cout<<i<<"%"<<j<<" "<<pts_list.size()<<endl;
- if (get_dist(pts_list[0],pts_list.back())<=ans+eps)
- continue;
- double cur_len=0;
- for (int i=0;i+1<pts_list.size();i++)
- {
- if (cur_len+get_dist(pts_list[i],pts_list.back())<=ans+eps)
- break;
- pt mid=mid_point(pts_list[i],pts_list[i+1]);
- //cout<<mid.x<<" "<<mid.y<<endl;
- if (!is_inside(mid))
- {
- cur_len=0;
- continue;
- }
- cur_len+=get_dist(pts_list[i+1],pts_list[i]);
- ans=max(ans,cur_len);
- }
- }
- }
- cout.precision(10);
- cout<<fixed<<ans<<endl;
- cin.get(); cin.get();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement