Pagini recente » Statistici Dahnovici Sandu (sandu__1337) | Diferente pentru utilizator/tudorv96 intre reviziile 28 si 27 | Istoria paginii dragosh/pwarmup2 | Monitorul de evaluare | Cod sursa (job #1081036)
#include <cstdio>
#include <algorithm>
#define nmax 120010
using namespace std;
struct punct
{
double x,y;
}a[nmax];
int n,st[nmax],nr,viz[nmax];
bool cmp(punct a, punct b)
{
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
void citire()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
}
bool verif(punct a, punct b, punct c)
{
if(a.x*b.y+b.x*c.y+a.y*c.x-c.x*b.y-b.x*a.y-c.y*a.x>=0)
return 1;
return 0;
}
void infas()
{
int i;
st[1]=1;
st[2]=2;
viz[2]=1;
viz[1]=1;
nr=2;
for(i=3;i<=n;i++)
{
while(!verif(a[st[nr-1]],a[st[nr]],a[i]) && nr>1)
viz[st[nr--]]=0;
st[++nr]=i;
viz[st[nr]]=1;
}
viz[1]=0;
for(i=n;i>=1;i--)
if(!viz[i])
{
while(!verif(a[st[nr-1]],a[st[nr]],a[i]) && nr>1)
viz[nr--]=0;
st[++nr]=i;
viz[nr]=1;
}
}
void afisare()
{
int i;
printf("%d\n",nr-1);
for(i=1;i<nr;i++)
printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
sort(a+1,a+1+n,cmp);
/*for(int i=1;i<=n;i++)
printf("%lf %lf\n",a[i].x,a[i].y);*/
infas();
afisare();
return 0;
}