Pagini recente » Cod sursa (job #811651) | Cod sursa (job #417594) | Cod sursa (job #2183723) | Cod sursa (job #2559424) | Cod sursa (job #1730793)
#include <bits/stdc++.h>
#define maxN 120005
#define f first
#define s second
using namespace std;
int n,i,j,top,poz=1;
pair<double,double> v[maxN],stk[maxN];
double det(pair<double,double>a,pair<double,double> b,pair<double,double>c)
{
return (b.f-a.f)*(c.s-a.s)-(c.f-a.f)*(b.s-a.s);
}
bool cmp(pair<double,double> a,pair<double,double>b)
{
return det(v[1],a,b)>0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf %lf",&v[i].f,&v[i].s);
if(v[i]<v[poz])
poz=i;
}
swap(v[poz],v[1]);
sort(v+2,v+n+1,cmp);
stk[++top]=v[1],stk[++top]=v[2];
for(i=3;i<=n;i++)
{
while(top>=2 && det(stk[top-1],stk[top],v[i])<0)
top--;
stk[++top]=v[i];
}
printf("%d\n",top);
for(i=1;i<=top;i++)
printf("%.6lf %.6lf\n",stk[i].f,stk[i].s);
return 0;
}