Pagini recente » Cod sursa (job #2127554) | Cod sursa (job #867062) | Cod sursa (job #2312666) | Cod sursa (job #913085) | Cod sursa (job #244665)
Cod sursa(job #244665)
#include <stdio.h>
#include <math.h>
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"
#define INF 2000000000
#define max 121000
struct puncte
{
float x;
float y;
}pct[max],stiva[max],p[max];
double aux[2][max];
FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");
int n,nr;
int varf,pozz;
int x00=INF,y00=INF;
int graham();
void pune(int);
void elimin();
double produs(int,int,int);
void sort();
double unghi(int);
int poz(int,int);
void quick(int,int);
int main()
{
int i;
fscanf(fin,"%d",&n);
for(i=1;i<=n;i++)
{
fscanf(fin,"%f %f",&pct[i].x,&pct[i].y);
if (pct[i].y<y00 || (pct[i].y==y00 && pct[i].x<x00))
x00=pct[i].x,y00=pct[i].y,pozz=i;
}
fclose(fin);
nr=graham();
fprintf(fout,"%d\n",nr);
for(i=1;i<=nr;i++)
fprintf(fout,"%f %f\n",stiva[i].x,stiva[i].y);
fclose(fout);
return 0;
}
int graham()
{
int i;
double o;
sort(); /// sorteaza in fct de unghiul polar si unde am acelasi unghi in fct de dist cea mai mare
varf=0;
pune(1); /// adauga in stiva pct p[i]
pune(2); /// am pus primele 2 pct
for(i=3;i<=n;i++)
{
o=produs(varf-1,varf,i); /// primele 2 din stiva iar restu din p[];
if(o==0)
{
elimin(); /// elimin pct apropiat
pune(i); /// pun pct departat
}
else
if(o>0) /// la stanga
pune(i);
else
{
while(o<=0 && varf>1) /// cat timp se poate si intoarcere la dreapta
{
elimin();
o=produs(varf-1,varf,i);
}
pune(i);
}
} /// de la for
return varf;
}
void pune(int i)
{
varf=varf+1;
stiva[varf].x=p[i].x;
stiva[varf].y=p[i].y;
}
void elimin()
{
varf=varf-1;
}
double produs(int i,int j,int k)
{
float x1,y1,x2,y2,x3,y3;
x1=stiva[i].x;
y1=stiva[i].y;
x2=stiva[j].x;
y2=stiva[j].y;
x3=p[k].x;
y3=p[k].y;
return (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
}
void sort()
{
int i;
for(i=1;i<=n;i++)
{
if(i==pozz)
{
aux[0][i]=i;
aux[1][i]=INF;
continue;
}
aux[0][i]=i;
aux[1][i]=unghi(i);
}
quick(1,n);
for(i=1;i<=n;i++)
{
p[i].x=pct[int (aux[0][n-i+1]) ].x;
p[i].y=pct[int (aux[0][n-i+1]) ].y;
}
}
double unghi(int i)
{
double x,y;
x=pct[i].x-x00;
y=sqrt( (pct[i].x-x00)*(pct[i].x-x00) + (pct[i].y-y00)*(pct[i].y-y00) );
return x/y;
}
void quick(int st,int dr)
{
if(st<dr)
{
int k;
k=poz(st,dr);
quick(st,k-1);
quick(k+1,dr);
}
}
int poz(int st,int dr)
{
int auxi;
double auxii;
int ii=1;
int jj=0;
while(st<dr)
{
if(aux[1][st]>aux[1][dr])
{
auxii=aux[1][st];
aux[1][st]=aux[1][dr];
aux[1][dr]=auxii;
auxii=aux[0][st];
aux[0][st]=aux[0][dr];
aux[0][dr]=auxii;
auxi=ii;
ii=-jj;
jj=-auxi;
}
st+=ii;
dr+=jj;
}
return st;
}