Pagini recente » Cod sursa (job #734466) | Cod sursa (job #2916232) | Cod sursa (job #753350) | Monitorul de evaluare | Cod sursa (job #1617997)
#include<cstdio>
#include<algorithm>
using namespace std;
struct punct{
double x,y;
}v[120001],sol[120001];
int n,vf;
double panta(punct a,punct b,punct c)
{
return (b.y-a.y)*(c.x-a.x)-(b.x-a.x)*(c.y-a.y);
}
bool cmp(punct a,punct b)
{
return panta(v[0],a,b)>0;
}
int main()
{
int poz=0;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (int i=0;i<n;i++)
{
scanf("%lf%lf",&v[i].x,&v[i].y);
if(v[i].x<v[poz].x||v[i].x==v[poz].x&&v[i].y<v[poz].y)
poz=i;
}
swap(v[0],v[poz]);
sort(v+1,v+n,cmp);
sol[0]=v[0];
sol[1]=v[1];
vf=1;
for(int i=2;i<n;i++)
{
while(vf>0&&panta(sol[vf-1],sol[vf],v[i])<0)vf--;
sol[++vf]=v[i];
}
printf("%d\n",vf+1);
for(int i=0;i<=vf;i++)
printf("%lf %lf\n",sol[i].x,sol[i].y);
return 0;
}