Pagini recente » Cod sursa (job #1585968) | Cod sursa (job #954768) | Cod sursa (job #329543) | Cod sursa (job #454619) | Cod sursa (job #1606070)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,varf,p,st[120001],ind[120001],l;
float x[120001],y[120001];
bool cmp(int a,int b)
{
return (y[a]-y[p])*(x[b]-x[p])<(y[b]-y[p])*(x[a]-x[p]);
}
bool det(int a,int b,int c)
{
return (x[a]*y[b]+x[b]*y[c]+x[c]*y[a]-x[c]*y[b]-x[a]*y[c]-x[b]*y[a])<0;
}
int main()
{
f>>n;
x[0]=1<<31-1,y[0]=1<<31-1;
for (i=1;i<=n;i++){
f>>x[i]>>y[i];
if (x[i]<x[p] || x[i]==x[p] && y[i]<y[p])
p=i;
}
for (i=1;i<=n;i++)
if (i!=p)
ind[++l]=i;
sort(ind+1,ind+n,cmp);
st[varf=1]=p;
for (i=1;i<=l;i++)
{
while(varf>=2 && det(st[varf-1],st[varf],ind[i]))
varf--;
st[++varf]=ind[i];
}
g<<varf<<'\n';
g<<fixed<<setprecision(12);
for (i=1;i<=varf;i++)
g<<x[st[i]]<<' '<<y[st[i]]<<'\n';
return 0;
}