Cod sursa(job #1919174)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 9 martie 2017 18:14:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const double eps=0.000000000001;
struct punct{double x,y;}v[120005];
int n,i,j,st[120005],top,step;
bool viz[120005];
inline bool cmp (punct A,punct B)
   {if(A.x==B.x)return A.y<B.y;
       else return A.x<B.x;
   }
inline bool Det(punct A,punct B, punct C)
      {return C.x*(A.y-B.y)+C.y*(B.x-A.x)+A.x*B.y-A.y*B.x<=eps;
      }
int main()
{fin>>n;
 for(i=1;i<=n;i++)
    {fin>>v[i].x>>v[i].y;
    }
 sort(v+1,v+n+1,cmp);
 st[1]=1;
 st[2]=2;
 top=2;
 step=1;
 viz[2]=1;
 for(i=3;i;i+=step)
    {if(viz[i]==1)continue;
     while(top>=2&&Det(v[st[top-1]],v[st[top]],v[i]))
          {viz[st[top]]=0;
           top--;
          }
     top++;
     st[top]=i;
     viz[i]=1;
     if(i==n)step=-1;
    }
    top--;
    fout<<top<<"\n";
 for(i=1;i<=top;i++)
    {
     fout<<setprecision(12)<<fixed;
     fout<<v[st[i]].x<<" ";
     fout<<setprecision(12)<<fixed;
     fout<<v[st[i]].y<<"\n";
    }
}