Pagini recente » Cod sursa (job #2514926) | Cod sursa (job #2176166) | Cod sursa (job #2708232) | Diferente pentru implica-te/arhiva-educationala intre reviziile 117 si 118 | Cod sursa (job #277019)
Cod sursa(job #277019)
#include<stdio.h>
#include<math.h>
#define nmax 120001
#define inf 0x3f3f
int st[nmax],n,k;
struct punct
{
double x,y;
float ung;
} a[nmax];
void graham(int i)
{
if (i<=n)
{
st[k+1]=i;
if ( ((a[st[k]].x-a[st[k+1]].x)*(a[st[k-1]].y-a[st[k]].y) + (a[st[k+1]].y-a[st[k]].y)*(a[st[k-1]].x-a[st[k]].x))>=0 )
{
st[k]=i;
graham(i+1);
}
else
{
++k;
graham(i+1);
}
}
}
void sort(int st,int dr)
{
if (st>=dr)
return ;
else
{
int poz=st-1;
for(int i=st;i<=dr;++i)
if (a[i].ung<=a[dr].ung)
{
punct aux=a[i];
a[i]=a[++poz];
a[poz]=aux;
}
sort(st,poz-1);
sort(poz+1,dr);
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
int min=inf,pmin=0;
for(int i=1;i<=n;++i)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
if (min>a[i].y)
{
min=a[i].y;
pmin=i;
}
else
if (min==a[i].y && a[pmin].x > a[i].x)
pmin=i;
}
for(int i=1;i<=n;++i)
{
if (a[i].x == a[pmin].x)
if (pmin!=i)
a[i].ung=90;
else
a[i].ung=-1;
else
{
a[i].ung=atan( double((a[i].y - a[pmin].y)) / (a[i].x - a[pmin].x) );
a[i].ung=(a[i].ung*180)/M_PI;
if (a[i].ung<0)
a[i].ung=a[i].ung+180;
}
}
sort(1,n);
st[1]=1;
st[2]=2;
st[3]=3;
k=3;
graham(4);
printf("%d\n",k);
for(int i=1;i<=k;++i)
printf("%.6f %.6f\n",a[st[i]].x,a[st[i]].y);
return 0;
}