Pagini recente » Cod sursa (job #3236576) | Cod sursa (job #1180362) | Cod sursa (job #1869582) | Cod sursa (job #3247884) | Cod sursa (job #1011474)
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define y first
#define x second
using namespace std;
typedef pair <double,double> punct;
punct a[120003];
int st[120003],use[120003],prim,ultim,n;
float x1,x2;
FILE *f,*g;
int verif (punct c,punct a,punct b)
{
double y1;
if (a.y==b.y) return c.y<=a.y;
else
{y1=((c.y-a.y)*(a.x-b.x))/(a.y-b.y) +a.x;
return y1>=c.x;}
}
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 (a+1,a+n+1);
st[1]=1;
st[2]=2;
prim=2;
ultim=2;use[2]=1;
for (i=3;i<=n;i++)
{ if (verif (a[i],a[st[prim-1]],a[st[prim]])) {st[++prim]=i;use[i]=1;}
else
{
while (!verif (a[i],a[st[prim-1]],a[st[prim]]) && prim>=2) {use[st[prim]]=0;
prim--;}
st[++prim]=i;
use[i]=1;
}
}
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]]) && use[i]==0) 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=1;i<=prim-1;i++) fprintf (g,"%0.6f %0.6f\n",a[st[i]].x,a[st[i]].y);
return 0;
}