Pagini recente » Cod sursa (job #2034093) | Cod sursa (job #2179352) | Cod sursa (job #261935) | Cod sursa (job #2711533) | Cod sursa (job #1011249)
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
struct punct {double x;double y;};
punct a[120003];
int st[120003],prim,ultim,n;
float x1,x2;
FILE *f,*g;
int verif (punct c,punct a,punct b)
{
double y1;
if (a.x==b.x) return c.x>=a.x;
else
{y1=((c.x-a.x)*(a.y-b.y))/(a.x-b.x) +a.y;
return y1>=c.y;}
}
void schimb (punct &v,punct &v1)
{
int aux;
aux=v.y;
v.y=v1.y;
v1.y=aux;
aux=v.x;
v.x=v1.x;
v1.x=aux;
}
void sort (int s,int d)
{
int m;
if (s<d)
{
int i=s,j=d,pi=0,pj=1;
while (i<j)
{
if (a[i].x>a[j].x) {schimb (a[i],a[j]);int aux=pi;pi=pj;pj=aux;}
else if (a[i].x==a[j].x && a[i].y>a[j].y) {schimb (a[i],a[j]);int aux=pi;pi=pj;pj=aux;}
i+=pi;
j-=pj;
}
m=i;
sort (s,m-1);
sort (m+1,d);
}
}
int main()
{f=fopen ("infasuratoare.in","r");
g=fopen ("infasuratoare.out","w");
fscanf (f,"%d",&n);
int i;
for ( i=1;i<=n;i++)
fscanf (f,"%lf%lf",&a[i].x,&a[i].y);
sort (1,n);
st[1]=1;
st[2]=2;
prim=2;
ultim=2;
for (i=3;i<=n;i++)
{ if (verif (a[i],a[st[prim-1]],a[st[prim]])) st[++prim]=i;
else
{
while (!verif (a[i],a[st[prim-1]],a[st[prim]]) && prim>=2)
prim--;
st[++prim]=i;
}
}
ultim=prim-1;
st[++prim]=n-1;
for (i=n-2;i>=1;i--)
{ if (!verif (a[i],a[st[prim-1]],a[st[prim]])) st[++prim]=i;
else
{
while (verif (a[i],a[st[prim-1]],a[st[prim]]) && prim-ultim>=2) prim--;
st[++prim]=i;
}
}
fprintf (g,"%d\n",prim-1);
for (i=prim-1;i>=1;i--) fprintf (g,"%0.6f %0.6f\n",a[st[i]].x,a[st[i]].y);
return 0;
}