URAL1067[Disk Tree]

水题,不说。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-4-3


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


#include <fstream>


using std::ifstream;


using std::ofstream;


#include <sstream>


using std::stringstream;


using std::endl;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <set>


using std::set;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <algorithm>


using std::sort;


#include <cassert>


//using std::assert;


 


struct FileTree


{


       string node;


       map<string,FileTree> child;


       void add(const string& path)


       {


            int end=path.find(‘\\’);


            if (end!=-1)


               child[path.substr(0,end)]


               .add(path.substr(end+1,path.length()));


            else


               child[path.substr(0,end)];


       }


       void print(const string& pre=“”)


       {


            for (map<string,FileTree>::iterator it=child.begin();


                 it!=child.end();it++)


            {


                cout<<pre<<it->first<<endl;


                it->second.print(” “+pre);


            }


       }


};


 


class Application


{


      int N;


      FileTree ft;


      public:


      Application()


      {


      }


      int run()


      {


          cin>>N;


          for (int i=0;i<N;i++)


          {


              string path;


              cin>>path;


              ft.add(path);


          }


          ft.print();


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

URAL1066[Garland]

数学题。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-4-8


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <iomanip>


 


#include <cstring>


using std::memset;


 


#define oo 1e10


#define MAXN 1000


 


int N;


double A;


double B;


 


void read()


{


     cin>>N>>A;


}


void write()


{


     cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);


     cout<<B<<endl;


}


void solve()


{


     /*


     h[i]=(h[i-1]+h[i+1])/2-1


     h[i]*2+2=(h[i-1]+h[i+1])


     h[i+1]=h[i]*2+2-h[i-1]


     h[i]=h[i-1]*2-h[i-2]+2


     h[i]-h[i-1]=h[i-1]-h[i-2]+2


    


     a[i]=h[i]-h[i-1]


     a[2]=h[2]-h[1]


       a[i]=a[i-1]+2


     所以a[i]=a[2]+(i-2)*2


     h[i]=h[i]-h[i-1]+h[i-1]-h[i-2]+…+h[2]-h[1]+h[1]


         =a[i]       +a[i-1]       +…+a[2]     +h[1]


         =sum{a[j],2<=j<=i}+h[1]


         =sum{(a[2]+(j-2)*2),2<=j<i}+h[1]


         =(i-2+1)*a[2]+(0+(i-2)*2)*(i-2+1)/2+h[1]


         =(i-1)*(h[2]-h[1])+(i-2)*(i-1)+h[1]


         =(i-1)*h[2]-(i-2)*h[1]+(i-2)*(i-1)


     */


     double h[MAXN+2];


     h[1]=A;


     B=oo;


     for (int i=2;i<=N;i++)//假设其中一个贴地


     {


         h[i]=0;


         h[2]=(h[i]-(i-2)*(i-1)+(i-2)*h[1])/(i-1);


        


         bool can=true;


         for (int j=2;j<=N;j++)


         {


             h[j]=(j-1)*h[2]-(j-2)*h[1]+(j-2)*(j-1);


             if (h[j]<0)


             {


                can=false;


                break;


             }


         }


         if (can)


            if (B>h[N]) B=h[N];


     }


}


 


int main()


{


    read();


    solve();


    write();


    return 0;


}


 


 

URAL1065[Frontier]

恩,有点计算几何的知识,还有动态规划。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-4-8


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <iomanip>


 


#include <cmath>


using std::sqrt;


#include <cstring>


using std::memset;


 


#define oo 1e10


#define MAXN 50


#define MAXM 1000


 


typedef long long int Type;


struct Point{Type x,y;};


 


int N,M;


Point outter[MAXN];


Point inner[MAXM];


double answer;


 


void read()


{


     cin>>N>>M;


     for (int i=0;i<N;i++)


         cin>>outter[i].x>>outter[i].y;


     for (int i=0;i<M;i++)


         cin>>inner[i].x>>inner[i].y;


}


void write()


{


     cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);


     cout<<answer<<endl;


}


 


Type cross(const Point& a,const Point& b,const Point& c)


{


     Type abx=b.x-a.x,


          aby=b.y-a.y,


          acx=c.x-a.x,


          acy=c.y-a.y;


     return abx*acy-aby*acx;


}


bool sameside(const Point& a,const Point& b,const Point& c,const Point& d)


{


     return cross(a,b,c)*cross(a,b,d)>=0;


}


bool inside(const Point& a,const Point& b,const Point& c,const Point& d)


{


     return sameside(a,b,c,d)&&sameside(a,c,b,d)&&sameside(b,c,a,d);


}


double distance(const Point& a,const Point& b)


{


       return sqrt(double((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));


}


void solve()


{


     bool can[MAXN][MAXN];


     memset(can,0,sizeof(can));


     for (int i=0;i<N;i++)


     {


         bool flag=true;


         for (int j=i+1;j<N+i;j++)


         {


             if (cross(outter[i],outter[j%N],outter[(j-1)%N])!=0)


                for (int k=0;k<M;k++)


                    if (inside(outter[i],outter[j%N],outter[(j-1)%N],inner[k]))


                    {


                       flag=false;


                       break;


                    }


             if (flag) can[i][j%N]=true;


         }


     }


    


     double map[MAXN][MAXN];


     for (int i=0;i<N;i++)


         for (int j=0;j<N;j++)


             if (can[i][j]) map[i][j]=distance(outter[i],outter[j]);


             else map[i][j]=oo;


     for (int k=0;k<N;k++)


         for (int i=0;i<N;i++)


             for (int j=0;j<N;j++)


                 if (map[i][k]+map[k][j]<map[i][j])


                    map[i][j]=map[i][k]+map[k][j];


    


     answer=oo;


     for (int i=0;i<N;i++)


         for (int j=i+1;j<N;j++)


             for (int k=j+1;k<N;k++)


                 if (cross(outter[i],outter[j],outter[k])!=0)


                    if (map[i][j]+map[j][k]+map[k][i]<answer)


                       answer=map[i][j]+map[j][k]+map[k][i];


}


 


 


int main()


{


    read();


    solve();


    write();


    return 0;


}


 


 

URAL1064[Binary Search]

其实,就是简单模拟。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-4-7


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


#include <fstream>


using std::ifstream;


using std::ofstream;


#include <sstream>


using std::stringstream;


using std::endl;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <set>


using std::set;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <algorithm>


using std::sort;


#include <cassert>


//using std::assert;


 


class Application


{


      static const int MAXN=10000;


      int i,L;


      int BinarySearch(int x,int N)


      {


          int p, q, i, L;         


          p = 0;   /* Left border of the search  */


          q = N-1; /* Right border of the search */


          L = 0;   /* Comparison counter         */


          while (p <= q)


          {


                i = (p + q) / 2;


                ++L;


                if (i == x)


                   return L;


                if (x < i)


                   q = i – 1;


                else


                    p = i + 1;


          }


          return1;


      }


      public:


      Application()


      {


                   cin>>i>>L;


      }


      int run()


      {


          int counter=0;


          stringstream sout;


          for (int j=0;j<=MAXN;j++)


          {


              if (BinarySearch(i,j)==L)


              {


                 sout<<j<<” “;


                 while ((j+1<=MAXN)&&(BinarySearch(i,j+1)==L)) j++;


                 sout<<j<<endl;


                 counter++;


              }


          }


          cout<<counter<<endl;


          cout<<sout.str();


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

URAL1063[Domino Puzzle]

图论题,先要知道,一个无向图存在欧拉路,当且仅当此图为强连通图,且度数为奇的节点数为0或2。


然后要做的就是先将图强联通,然后贪心加边。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-4-6


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


#include <fstream>


using std::ifstream;


using std::ofstream;


#include <sstream>


using std::stringstream;


using std::endl;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <set>


using std::set;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <algorithm>


using std::sort;


#include <cassert>


//using std::assert;


 


class Application


{


      static const int oo=~(1<<31);


      static const int SIDE=6;


      vector<vector<int> > c;


      vector<int> degree;


      //GET PART


      vector<int> getid;


      void dfs(int id,stack<int>& s)


      {


           static vector<bool> visited(SIDE,false);


           if (!visited[id])


           {


              visited[id]=true;


              s.push(id);


              for (int i=0;i<SIDE;i++)


                  if (c[id][i])


                     dfs(i,s);


           }


      }


      void get_part()


      {


           vector<vector<int> > part;


           getid.resize(SIDE);


           stack<int> s;


           for (int i=0;i<SIDE;i++)


           {


               if (degree[i])


               {


                  dfs(i,s);


                  if (!s.empty())


                  {


                     part.push_back(vector<int>());


                     while (!s.empty())


                           part.back().push_back(s.top()),


                           getid[s.top()]=part.size(),


                           s.pop();


                  }


               }


           }


      }


      //END GET PART


      //GET ANSWER


      int answer;


      vector<pair<int,int> > list;


      bool check()


      {


           vector<vector<bool> > link(SIDE,vector<bool>(SIDE,false));


          


           for (int i=0;i<SIDE;i++)


               for (int j=0;j<SIDE;j++)


                   link[i][j]=c[i][j]||i==j;


          


           for (int k=0;k<SIDE;k++)


               for (int i=0;i<SIDE;i++)


                   for (int j=0;j<SIDE;j++)


                       if (link[i][k]&&link[k][j])


                          link[i][j]=true;


          


           for (int i=0;i<SIDE;i++)


               for (int j=0;j<SIDE;j++)


                   if (degree[i]&&degree[j]&&(!link[i][j])) return false;


          


           return true;


      }


      void update(vector<pair<int,int> >& record)


      {


           int nanswer=0;


           for (int i=0;i<record.size();i++)


               nanswer+=record[i].first+1+record[i].second+1;


           vector<pair<int,int> > nlist(record);


          


           int counter=0;


           for (int i=0;i<SIDE;i++)


               if (degree[i]%2) counter++;


           vector<int> add;


           for (int i=0;i<SIDE;i++)


           {


               if (counter==2||counter==0) break;


               if (degree[i]%2)


               {


                  nanswer+=i+1;


                  counter–;


                  add.push_back(i);


               }


           }


           for (int i=0;i<add.size();i+=2)


               nlist.push_back(make_pair(add[i],add[i+1]));


          


           if (nanswer<answer)


           {


              answer=nanswer;


              list=nlist;


           }


      }


      void search(const vector<int>& getid)


      {


           static vector<pair<int,int> > record;


           set<int> part;


           for (int i=0;i<SIDE;i++)


               if (getid[i])


                  part.insert(getid[i]);


          


           if (part.size()>1)


           {


              for (int i=0;i<SIDE;i++)


                  for (int j=i+1;j<SIDE;j++)


                      if (degree[i]&&degree[j]&&getid[i]!=getid[j])


                      {


                         vector<int> ngetid=getid;


                         for (int k=0;k<SIDE;k++)


                             if (getid[k]==getid[i])


                                ngetid[k]=ngetid[j];


                         c[i][j]++;


                         c[j][i]++;


                         degree[i]++;


                         degree[j]++;


                         record.push_back(make_pair(i,j));


                         search(ngetid);


                         record.pop_back();


                         degree[j]–;


                         degree[i]–;


                         c[j][i]–;


                         c[i][j]–;


                      }


           }


           else


           {


               if (check())


                  update(record);


           }


      }


      //END GET ANSWER


      public:


      Application()


                   :c(SIDE,vector<int>(SIDE,0)),degree(SIDE,0)


      {


                   int N;


                   cin>>N;


                   for (int i=0;i<N;i++)


                   {


                       int u,v;


                       cin>>u>>v;


                       c[u-1][v-1]++;


                       c[v-1][u-1]++;


                       degree[u-1]++;


                       degree[v-1]++;


                   }


      }


      int run()


      {


          get_part();


          answer=oo;


          search(getid);


          cout<<answer<<endl;


          cout<<list.size()<<endl;


          for (int i=0;i<list.size();i++)


              cout<<list[i].first+1<<” “<<list[i].second+1<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

URAL1062[Triathlon]

半平面交,然后先暂时用O(n^2)的过了。


半平面交O(n^2),一共这样做n次,总的时间复杂度O(n^3)。


半平面交有O(nlogn)的分治法,不过现在还不会。


然后讲一下O(n^2)的半平面交:


先有一个凸包{(-oo,-oo),(oo,-oo),(oo,oo),(-oo,oo)}(点有序),然后用线依次去切。


对凸包上的点:


1.如果它不被切掉,保留它(如下图中的绿线切C点);


2.它被切掉,先丢掉它(如下图中的红线切A点),然后如果与它相邻的点不被切掉(相邻指按级角排序后的顺序中相邻),那么加入它与相邻点所在直线与切割线的交点(如下图中的蓝线切B点,加入的是两个红点)。


URAL1062[Triathlon] - 天之骄子 - 天之骄子的家


主要思路就是这样了。


CODE:


//DATE:2010-4-1


#include <cstdio>


using std::printf;


using std::scanf;


#include <cstring>


using std::memcpy;


 


#define MAXN 100


#define KIND 3


#define oo 1e10


#define zero 1e-10


 


typedef int Player[MAXN][KIND];


struct Point{double x,y;};


struct Line{double a,b,c;};


 


int N;


Player player;


Line line[MAXN];


bool canWin[MAXN];


 


void read()


{


     scanf(“%d”,&N);


     for (int i=0;i<N;i++)


         for (int j=0;j<KIND;j++)


             scanf(“%d”,&player[i][j]);


}


void write()


{


     for (int i=0;i<N;i++)


         if (canWin[i]) printf(“Yes\n”);


         else printf(“No\n”);


}


void initLines()


{


     for (int i=0;i<N;i++)


         line[i].a=1.0/player[i][0],


         line[i].b=1.0/player[i][1],


         line[i].c=1.0/player[i][2];


}


Point intersect(Line l,Point a,Point b)


{


      Point get;


      double fa=l.a*a.x+l.b*a.y+l.c;


      double fb=l.a*b.x+l.b*b.y+l.c;


      get.x=(fb*a.x-fa*b.x)/(fb-fa);


      get.y=(fb*a.y-fa*b.y)/(fb-fa);


      return get;


}


void cut(Point* p,int& pn,Line cutter)


{


     Point q[MAXN+4];


     int qn=0;


     for (int i=0;i<pn;i++)


     {


         if (p[i].x*cutter.a+p[i].y*cutter.b+cutter.c>zero)


            q[qn++]=p[i];


         else


         {


             int before=(i-1+pn)%pn;


             int next=(i+1)%pn;


             if (p[before].x*cutter.a+p[before].y*cutter.b+cutter.c>zero)


                q[qn++]=intersect(cutter,p[before],p[i]);


             if (p[next].x*cutter.a+p[next].y*cutter.b+cutter.c>zero)


                q[qn++]=intersect(cutter,p[i],p[next]);


         }


     }


     memcpy(p,q,sizeof(q));


     pn=qn;


}


bool isEmpty(Line* l,int n)


{


     Point p[MAXN+4];


     int pn=0;


     p[pn].x=0;


     p[pn].y=0;


     pn++;


     p[pn].x=oo;


     p[pn].y=0;


     pn++;


     p[pn].x=oo;


     p[pn].y=oo;


     pn++;


     p[pn].x=0;


     p[pn].y=oo;


     pn++;


     for (int i=0;i<n;i++)


         cut(p,pn,l[i]);


     return pn<3;


    


}


bool can(int id)


{


     Line l[MAXN];


     memcpy(l,line,sizeof(line));


     for (int i=0;i<N;i++)


         if (i!=id)


            l[i].a-=l[id].a,


            l[i].b-=l[id].b,


            l[i].c-=l[id].c;


     l[id]=l[N-1];


     if (isEmpty(l,N-1)) return false;


     else return true;


}


void solve()


{


     initLines();


     for (int i=0;i<N;i++)


         canWin[i]=can(i);


}


int main()


{


    read();


    solve();


    write();


    return 0;


}


 


 

URAL1061[Buffer Manager]

水题,数学题,在长度为L的数列中求长度为K的和最小的连续子数列。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-30


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


#include <fstream>


using std::ifstream;


using std::ofstream;


#include <sstream>


using std::stringstream;


using std::endl;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <set>


using std::set;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <algorithm>


using std::sort;


#include <cassert>


//using std::assert;


 


class Application


{


      static const long long int oo=1000000000;


      int N,K,L;


      vector<long long int> data;


      vector<long long int> sum;


      public:


      Application()


      {


                   cin>>N>>K;


                   data.resize(N);


                   for (int i=0;i<N;i++)


                   {


                       char c;


                       cin>>c;


                       if (c==’*’) data[i]=oo;


                       else data[i]=c-‘0’;


                   }


      }


      int run()


      {


          sum.resize(N+1);


          sum[0]=0;


          for (int i=0;i<N;i++)


              sum[i+1]=sum[i]+data[i];


         


          long long int min=oo;


          L=0;


          for (int i=0;i<=N-K;i++)


              if (sum[i+K]-sum[i]<min)


              {


                 L=i+1;


                 min=sum[i+K]-sum[i];


              }


          cout<<L<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

URAL1060[Flip Game]

水题,BFS就行了。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-30


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


#include <fstream>


using std::ifstream;


using std::ofstream;


#include <sstream>


using std::stringstream;


using std::endl;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <set>


using std::set;


#include <map>


//using std::map;


using std::pair;


using std::make_pair;


#include <algorithm>


using std::sort;


#include <cassert>


//using std::assert;


 


struct State


{


       static const int SIZE=4;


       bool map[SIZE][SIZE];


       int id;


       void getId()


       {


            id=0;


            for (int i=0;i<SIZE;i++)


                for (int j=0;j<SIZE;j++)


                {


                    id<<=1;


                    if(map[i][j]) id++;


                }


       }


       void read()


       {


            for (int i=0;i<SIZE;i++)


                for (int j=0;j<SIZE;j++)


                {


                    char c;


                    cin>>c;


                    map[i][j]=(c==’w’);


                }


            getId();


       }


       void set(bool what)


       {


            for (int i=0;i<SIZE;i++)


                for (int j=0;j<SIZE;j++)


                    map[i][j]=what;


            getId();


       }


       void turn(int x,int y)


       {


            map[x][y]=!map[x][y];


            if (x-1>=0) map[x-1][y]=!map[x-1][y];


            if (x+1<SIZE) map[x+1][y]=!map[x+1][y];


            if (y-1>=0) map[x][y-1]=!map[x][y-1];


            if (y+1<SIZE) map[x][y+1]=!map[x][y+1];


            getId();


       }


       void print()


       {


            for (int i=0;i<SIZE;i++)


            {


                for (int j=0;j<SIZE;j++)


                    cout<<map[i][j];


                cout<<endl;


            }


       }


};


 


class Application


{


      static const int NOTREACH=~(1<<31);


      State s,t1,t2;


      public:


      Application()


      {


                   s.read();


                   t1.set(true);


                   t2.set(false);


      }


      int run()


      {


          vector<int> step(1<<((State::SIZE)*(State::SIZE)),NOTREACH);


          queue<State> q;


         


          q.push(s);


          step[s.id]=0;


         


          while (!q.empty())


          {


                State& now=q.front();


                for (int i=0;i<State::SIZE;i++)


                    for (int j=0;j<State::SIZE;j++)


                    {


                        State get=now;


                        get.turn(i,j);


                        if (step[get.id]==NOTREACH)


                        {


                           q.push(get);


                           step[get.id]=step[now.id]+1;


                        }


                    }


                q.pop();


          }


          int answer=step[t1.id]<step[t2.id]?step[t1.id]:step[t2.id];


          if (answer==NOTREACH) cout<<“Impossible”<<endl;


          else cout<<answer<<endl;


         


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

URAL1059[Expression]

后缀表达式。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-30


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


#include <fstream>


using std::ifstream;


using std::ofstream;


#include <sstream>


using std::stringstream;


using std::endl;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <set>


using std::set;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <algorithm>


using std::sort;


#include <cassert>


//using std::assert;


 


class Application


{


      int N;


      public:


      Application()


      {


                   cin>>N;


      }


      int run()


      {


          cout<<0<<endl;


          for (int i=1;i<=N;i++)


              cout<<“X”<<endl<<“*”<<endl<<i<<endl<<“+”<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

URAL1058[Chocolate]

由于数据加强了,这个程序已经不能AC了。(我又写了一个程序,这个能AC了。)

麻烦的几何题,先选两条边,再定比分点,其中一个点枚举,另一个用面积算,然后算它们的距离更新最优解,注意精度。(原来朴素的枚举,不是超时,就是精度不够,后来写的程序用了三分法。

还有有更好的算法,不用枚举点,不过仿佛写着更累,因为WSC就写了很久。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2011-10-27

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <cmath>

using namespace std;

 

#define point pair<double,double>

#define x first

#define y second

 

const int MAXN=50;

int N;

point P[MAXN];

 

double cross(point a,point b,point c)

{

    return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);

}

double sqr(double x)

{

    return x*x;

}

double calc(int A,int B,int C,int D,double S,double SAB,double t1)

{

    point M,N;

    M.x=P[B].x*(1-t1)+P[C].x*t1;

    M.y=P[B].y*(1-t1)+P[C].y*t1;

    double S1=abs(cross(P[A],P[B],P[C])/2)*t1;

    double S2=S/2-SAB-S1;

    double t2=S2/(abs(cross(P[A],M,P[D])/2));

    N.x=P[A].x*(1-t2)+P[D].x*t2;

    N.y=P[A].y*(1-t2)+P[D].y*t2;

    return sqrt(sqr(M.x-N.x)+sqr(M.y-N.y));

}

int main()

{

    cin>>N;

    for (int i=0;i<N;i++)

       cin>>P[i].x>>P[i].y;

    double S;

    for (int i=0;i<N;i++)

       S+=abs(cross(P[0],P[i],P[(i+1)%N])/2);

    double answer=1e10;

    for (int A=0;A<N;A++)

    {

       double SAB=0;

       int D=(A+N-1)%N;

       for (int B=(A+1)%N;;B=(B+1)%N)

       {

           int C=(B+1)%N;

           double SCD=S-SAB-abs(cross(P[A],P[B],P[C])/2)-abs(cross(P[A],P[C],P[D])/2);

           if (SAB>S*0.5) break;

           else if (SCD<=S*0.5)

           {

              double L=max(0.0,1.0-(SAB+abs(cross(P[A],P[B],P[C])/2)+abs(cross(P[A],P[C],P[D])/2)-S/2)/abs(cross(P[D],P[B],P[C])/2)),R=min(1.0,(S/2-SAB)/abs(cross(P[A],P[B],P[C])/2));

              for (;;)

              {

                  double LM=(L*2+R)/3;

                  double RM=(L+R*2)/3;

                  double LV=calc(A,B,C,D,S,SAB,LM);

                  double RV=calc(A,B,C,D,S,SAB,RM);

                  if (abs(LM-RM)<=0.0000001&&abs(LV-RV)<0.0000001)

                  {

                     if (answer>LV) answer=LV;

                     break;

                  }

                  else if (LV<RV) R=RM;

                  else L=LM;

              }

           }

           SAB+=abs(cross(P[A],P[B],P[C])/2);

       }

    }

    cout.setf(ios::fixed);

    cout.precision(4);

    cout<<answer<<endl;

    return 0;

}