Pagini recente » Cod sursa (job #193266) | Cod sursa (job #3299022) | Cod sursa (job #2561558) | Cod sursa (job #736527) | Cod sursa (job #3300598)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
double x[120005],y[120005];
int stiva[120005],dim;
bool pus[120005];
bool compara(int a,int b)
{
if(x[a]!=x[b]) return x[a]<x[b];
return y[a]<y[b];
}
double det(int a,int b,int c)
{
return (x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a]);
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++) fin>>x[i]>>y[i];
int ord[120005];
for(int i=1;i<=n;i++) ord[i]=i;
sort(ord+1,ord+n+1,compara);
for(int i=1;i<=n;i++)
{
int pct=ord[i];
while(dim>=2&&det(stiva[dim-2],stiva[dim-1],pct)<=0)
pus[stiva[--dim]]=false;
stiva[dim++]=pct;
pus[pct]=true;
}
int start=dim;
for(int i=n-1;i>=1;i--)
{
int pct=ord[i];
if(pus[pct]) continue;
while(dim>=start+1&&det(stiva[dim-2],stiva[dim-1],pct)<=0)
pus[stiva[--dim]]=false;
stiva[dim++]=pct;
pus[pct]=true;
}
if(dim>=2&&x[stiva[0]]==x[stiva[dim-1]]&&y[stiva[0]]==y[stiva[dim-1]])
dim--;
fout<<dim<<endl;
fout<<setprecision(6)<<fixed;
for(int i=0;i<dim;i++)
fout<<x[stiva[i]]<<" "<<y[stiva[i]]<<endl;
fin.close();
fout.close();
return 0;
}