Pagini recente » Cod sursa (job #1000275) | Cod sursa (job #2352888) | Cod sursa (job #540463) | Cod sursa (job #2257738) | Cod sursa (job #288996)
Cod sursa(job #288996)
#include<stdio.h>
#define infile "infasuratoare.in"
#define outfile "infasuratoare.out"
#define nmax 120*1001
struct pct
{
double x,y; //coordonatele punctului
} v[nmax]; //vectorul cu punctele ;))
struct pct s[nmax]; int k; //stiva
struct pct pi; //punctul cel mai din stanga, respectiv cel mai de jos ;))
int n; //numarul de puncte
void citire()
{
int i;
scanf("%d\n",&n);
for(i=1;i<=n;i++)
scanf("%lf %lf",&v[i].x,&v[i].y);
}
void punct_initial()
{
int i,j;
pi=v[1]; //initial este primul punct ;))
for(i=2;i<=n;i++)
if(v[i].x<pi.x || (v[i].x==pi.x && v[i].y<=pi.y)) //am gasit un punct mai in stanga/jos
{
pi=v[i]; //salvam punctul ;))
j=i; //salvam si pozitia ;))
}
//mutam toate punctele de dupa el cu o pozitie in stanga ;))
n--; //dispare punctul ;))
for(i=j;i<=n;i++)
v[i]=v[i+1];
}
int divide(int p, int q)
{
struct pct a=v[p]; //punctul ce trebuie plasat corect ;))
while(p<q)
{
while(p<q && ((v[q].x-pi.x) * (a.y-pi.y)) <= ((a.x-pi.x) * (v[q].y-pi.y))) q--; //panta punctului din drepata este mai mare ;))
v[p]=v[q]; //am gasit in dreapta o panta mai mica ;))
while(p<q && ((v[p].x-pi.x) * (a.y-pi.y)) >= ((a.x-pi.x) * (v[p].y-pi.y))) p++; //panta punctului din stanga este mai mica
v[q]=v[p]; //punctul din stanga este mai mare ;))
}
v[p]=a; //plasam corect punctul ;))
return p; //returnam pozitia ;))
}
void qsort(int p, int q)
{
int m=divide(p,q);
if(p<m-1) qsort(p,m-1); //sortam partea stanga
if(m+1<q) qsort(m+1,q); //sortam partea dreapta
}
double verif(struct pct a, struct pct b, struct pct p)
{
return a.x*b.y + b.x*p.y + p.x*a.y - b.y*p.x - p.y*a.x - a.y*b.x;
}
void solve()
{
int i;
s[k=1]=pi; //initial in stiva avem primul punct ;))
for(i=1;i<=n;i++)
{
while(k>1&&verif(s[k-1],s[k],v[i])<=0) k--; //daca noul punct merge in sens invers trogonometric
s[++k]=v[i]; //salvam punctul
}
}
void afisare()
{
int i;
printf("%d\n",k); //numarul de pucnte de pe infasuratoare
for(i=1;i<=k;i++) //afisem punctele ;))
printf("%lf %lf\n",s[i].x,s[i].y);
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
citire();
punct_initial(); //aflam primul punct de pe infasuratoare
qsort(1,n); //sortam punctele dupa panta fata de primul punct de pe infasuratoare
solve(); //salvam in stiva infasuratoarea convexa ;))
afisare();
fclose(stdin);
fclose(stdout);
return 0;
}