Pagini recente » Cod sursa (job #2286036) | Cod sursa (job #2187170) | Cod sursa (job #71758) | Cod sursa (job #1708701) | Cod sursa (job #431447)
Cod sursa(job #431447)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n,h,st[120050],sol[120050];
struct punct
{
double x,y;
};
punct v[120050];
void citire()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%lf%lf",&v[i].x,&v[i].y);
}
bool comp (const punct &a,const punct &b)
{
if (a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
double dreapta (int i,int j)
{
return v[st[i-2]].x*v[st[i-1]].y+v[st[i-1]].x*v[j].y+v[j].x*v[st[i-2]].y-v[j].x*v[st[i-1]].y-v[st[i-1]].x*v[st[i-2]].y-v[st[i-2]].x*v[j].y;
}
int main()
{
citire();
sort(v+1,v+1+n,comp);
st[1]=1;
st[2]=2;
int i=3,j=3;
do
{
while (dreapta(i,j)<0&&i>2)
st[i--]=0;
st[i++]=j++;
}
while (j<=n);
for (int i=1;st[i];++i)
sol[++h]=st[i];
memset(st,0,sizeof(st));
st[1]=1;
st[2]=2;
i=3;
j=3;
do
{
while (dreapta(i,j)>0&&i>2)
st[i--]=0;
st[i++]=j++;
}
while (j<=n);
i-=2;
for (;i>1;--i)
sol[++h]=st[i];
printf("%d\n",h);
for (int i=1;i<=h;++i)
printf("%lf %lf\n",v[sol[i]].x,v[sol[i]].y);
return 0;
}