Cod sursa(job #288996)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 26 martie 2009 11:54:45
Problema Infasuratoare convexa Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 2.42 kb
#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;
}