Pagini recente » Cod sursa (job #284453) | Cod sursa (job #24420) | Cod sursa (job #3277664) | Cod sursa (job #1580786) | Cod sursa (job #1011460)
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
struct punct {double x;double y;};
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;}
}
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].y>a[j].y) {schimb (a[i],a[j]);int aux=pi;pi=pj;pj=aux;}
else if (a[i].y==a[j].y && a[i].x<a[j].x) {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;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;
}