Pagini recente » Cod sursa (job #1167157) | Cod sursa (job #989208) | Cod sursa (job #989072) | Cod sursa (job #259723) | Cod sursa (job #659655)
Cod sursa(job #659655)
#include <stdio.h>
#include <stdlib.h>
#define inf 2000000000;
typedef struct conv
{
double x,y,p;
}conv;
conv a[100000],st[100000],m;
int n,poz,nr=2;
void citire()
{
m.x=inf;
m.y=inf;
freopen("infasuratoare.in","r",stdin);
scanf("%d",&n);
int i;
for(i=0;i<n;i++)
{
scanf("%lf %lf",&a[i].x,&a[i].y);
if(a[i].x<m.x || (a[i].x==m.x && a[i].y<m.y))
{
m=a[i];
poz=i;
}
}
a[poz]=a[n-1];
n--;
}
void panta()
{
int i;
for(i=0;i<n;i++)
{
if(a[i].x==m.x)
{
a[i].p=inf;
}
else
{
a[i].p=(a[i].y-m.y)/(a[i].x-m.x);
}
}
}
void sortare()
{
int i,j;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(a[i].p>a[j].p)
{
double aux=a[i].x;
a[i].x=a[j].x;
a[j].x=aux;
aux=a[i].y;
a[i].y=a[j].y;
a[j].y=aux;
aux=a[i].p;
a[i].p=a[j].p;
a[j].p=aux;
}
}
int det(conv a,conv b,conv c)
{
double d=a.x * b.y + a.y * c.x + b.x * c.y - a.y * b.x - b.y * c.x - c.y * a.x;
if(d>=0)
return 1;
return 0;
}
void infasuratoare()
{
st[0]=m;
st[1]=a[0];
int i;
for(i=1;i<n;i++)
if(det(st[nr-2],st[nr-1],a[i])==1)
st[nr++]=a[i];
else
{
while(det(st[nr-2],st[nr-1],a[i])==0)
st[--nr]=a[i];
nr++;
}
}
void afisare()
{
freopen("infasuratoare.out","w",stdout);
printf("%d\n",nr);
int i;
for(i=0;i<nr;i++)
printf("%lf %lf\n", st[i].x, st[i].y);
}
int main()
{
citire();
panta();
sortare();
infasuratoare();
afisare();
return 0;
}