Pagini recente » Cod sursa (job #734576) | Cod sursa (job #1799261) | Cod sursa (job #486239) | Cod sursa (job #2391344) | Cod sursa (job #659675)
Cod sursa(job #659675)
#include <stdio.h>
#include <stdlib.h>
#define inf 2000000000;
typedef struct conv
{
double x,y,p;
}conv;
conv a[120001],st[120001],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);
}
}
}
int partitionare(int st,int dr,conv a[])
{
int j=dr+1,i=st-1,ok=1,k;
double pivot;
pivot=a[st].p;
do
{
do
{
j--;
}
while(a[j].p>pivot);
do
{
i++;
}
while(a[i].p<pivot);
if(i<j)
{
conv aux=a[i];
a[i]=a[j];
a[j]=aux;
}
else
{
ok=0;
k=j;
}
}
while(ok==1);
return k;
}
void sortare(conv a[],int st,int dr)
{
if(st<dr)
{
int p=partitionare(st,dr,a);
sortare(a,st,p);
sortare(a,p+1,dr);
}
}
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(a,0,n-1);
infasuratoare();
afisare();
return 0;
}