Pagini recente » Cod sursa (job #1610568) | Cod sursa (job #1057329) | Cod sursa (job #722936) | Cod sursa (job #5769) | Cod sursa (job #3300599)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
double x[120005],y[120005];
int stiva[120005],dim;
int pivot;
double distanta(int a, int b)
{
return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
}
int orientare(int p, int q, int r)
{
double val = (y[q]-y[p])*(x[r]-x[q])-(x[q]-x[p])*(y[r]-y[q]);
if(abs(val)<1e-12) return 0;
return (val>0) ? 1 : 2;
}
bool compara(int a, int b)
{
int o = orientare(pivot, a, b);
if(o==0) return distanta(pivot, a)<distanta(pivot, b);
return (o==1);
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>x[i]>>y[i];
int minim=1;
for(int i=2;i<=n;i++)
{
if(y[i]<y[minim] || (y[i]==y[minim] && x[i]<x[minim]))
minim=i;
}
pivot=minim;
int ord[120005];
int cnt=0;
for(int i=1;i<=n;i++)
if(i!=pivot) ord[++cnt]=i;
sort(ord+1,ord+cnt+1,compara);
stiva[dim++]=pivot;
stiva[dim++]=ord[1];
for(int i=2;i<=cnt;i++)
{
int pct=ord[i];
while(dim>=2 && orientare(stiva[dim-2],stiva[dim-1],pct)!=1)
dim--;
stiva[dim++]=pct;
}
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;
}