Cod sursa(job #617590)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 15 octombrie 2011 04:46:51
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.67 kb
#include<stdio.h>
#include<cmath>

#define PI 3.14159265

using namespace std;

struct punct
{
	double x,y;
	punct *leg;
};

int N;
punct *puncte, *P, *sol;

void Citire()
{
	freopen ("infasuratoare.in","r",stdin);
	scanf("%d",&N);
	
	puncte = new punct;
	scanf("%lf %lf",&puncte->x,&puncte->y);
	puncte->leg=NULL;
	for (int i=1;i<N;i++) 
		{
			punct *p = new punct;
			scanf("%lf %lf",&p->x,&p->y);
			p->leg = puncte;
			puncte = p;
		}	
	fclose(stdin);
}


double Unghi(punct *C, punct *N)
{
	double PC, CN, NP, unghiC;
	
	PC = sqrt((C->x-P->x)*(C->x-P->x) + (C->y-P->y)*(C->y-P->y));
	NP = sqrt((N->x-P->x)*(N->x-P->x) + (N->y-P->y)*(N->y-P->y));
	CN = sqrt((C->x-N->x)*(C->x-N->x) + (C->y-N->y)*(C->y-N->y));
	
	double cosx = (PC*PC + CN*CN - NP*NP)/(2*PC*CN);
	unghiC = acos(cosx) * 180.0 / PI;
	return unghiC;
}


punct *PunctUrmator(punct *C)
{
	punct *punctMax, *p, *r, *prec;
	double unghiTemp, unghiMax = -1;
	
	for (p = puncte->leg, r = puncte; p != NULL ; p = p->leg, r=r->leg)
	{
		if (sol->leg == NULL) P = r;
		else {P->x = sol->leg->x;P->y = sol->leg->y;}
		unghiTemp = Unghi(C,p);
		if (unghiTemp > unghiMax) 
			{
				unghiMax = unghiTemp;
				punctMax = p;
				prec = r;
			}
	}
		p=puncte;
		unghiTemp = Unghi(C,p);
		if (unghiTemp > unghiMax) 
			{
				unghiMax = unghiTemp;
				punctMax = p;
				puncte = puncte->leg;
				return punctMax;
			}
		
	P = C;
	prec -> leg = punctMax->leg;
	return punctMax;
}

punct *PunctInitial()
{
	punct *punctStart = puncte, *p = puncte;
	while (p!=NULL)
	{
		if (p->x > punctStart->x)
			punctStart = p;
		if (p->x == punctStart->x && p->y < punctStart->y)
			punctStart = p;
		p=p->leg;
	}
	
	return punctStart; 
}

int main()
{
	Citire();
	int nrSol = 0;
	punct *punctInitial = new punct,*p;
	p = PunctInitial();
	punctInitial->x=p->x;
	punctInitial->y=p->y;
	P = punctInitial;
	
	sol = new punct;
	sol->x = punctInitial->x;
	sol->y = punctInitial->y;
	sol->leg = NULL;
	P->y ++;
	
	punct *punctMobil = PunctUrmator(p);
	punctMobil ->leg = sol;
	sol = punctMobil;
	nrSol = 2;
	P = punctInitial;
	
	do 
	{
		punctMobil = PunctUrmator(punctMobil);
		punctMobil ->leg = sol;
		sol = punctMobil;
		nrSol++;
	}
	while (punctMobil->x != punctInitial->x || punctMobil->y != punctInitial->y);
	
	freopen("infasuratoare.out", "w", stdout);
	printf ("%d\n",nrSol - 1);
	p = sol;
	punct *q = p->leg, *r = p->leg->leg;
	p->leg = NULL;
	
	while (r!=NULL)
	{
		q->leg = p;
		p = q;
		q = r;
		r = r->leg;
	}
	q->leg = p;
	while(q->leg != NULL)
	{
		printf("%.6lf %.6lf\n",q->x,q->y);
		q = q->leg;
	}
	
	fclose(stdout);
	return 0;
}