Pagini recente » Cod sursa (job #1818739) | Cod sursa (job #799656) | Cod sursa (job #1549011) | Cod sursa (job #982115) | Cod sursa (job #1910921)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int Nmax=120005,oo=1<<30;
int N,PI,ind[Nmax],St[Nmax];
double X[Nmax],Y[Nmax];
bool comp(int a,int b)
{
return (double)(X[a]-X[PI])*(Y[b]-Y[PI])<(double)(X[b]-X[PI])*(Y[a]-Y[PI]);
}
long double semn(int a,int b,int c)
{
return (long double)X[a]*Y[b]-X[b]*Y[a]+X[b]*Y[c]-X[c]*Y[b]+X[c]*Y[a]-X[a]*Y[c];
}
void read()
{
fin>>N;
X[0]=Y[0]=oo;
for(int i=1;i<=N;i++)
{
fin>>X[i]>>Y[i];
if(X[i]<X[PI] || (X[i]==X[PI] && Y[i]<Y[PI])) PI=i;
}
for(int i=1;i<=N;i++)
{
if(i!=PI)
ind[++ind[0]]=i;
}
sort(ind+1,ind+ind[0]+1,comp);
St[++St[0]]=PI;
for(int i=1;i<=ind[0];i++)
{
if(ind[i]!=PI)
{
while(St[0]>2 && semn(St[St[0]-1],St[St[0]],ind[i])>0)
St[0]--;
St[++St[0]]=ind[i];
}
}
St[++St[0]]=PI;
fout<<St[0]-1<<"\n";
reverse(St+1,St+St[0]+1);
for(int i=1;i<St[0];i++)
fout<<fixed<<setprecision(6)<<X[St[i]]<<" "<<Y[St[i]]<<"\n";
}
int main()
{
read();
return 0;
}