Cod sursa(job #617584)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 15 octombrie 2011 02:26:18
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include<fstream>
#include<stdio.h>
#include<cmath>

#define PI 3.14159265

using namespace std;

struct punct
{
	double x,y;
	bool vizitat;
};

int N;
punct puncte[120001], P, sol[120000];

void Citire()
{
	ifstream fin("infasuratoare.in");
	fin>>N;
	
	int i;
	
	for (i=0;i<N;i++) 
		{
			fin>>puncte[i].x>>puncte[i].y;
			puncte[i].vizitat = false;
		}
	
	fin.close();
}

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);
	return unghiC;
}

punct PunctUrmator(punct C)
{
	int i, iTemp = 120001;
	punct punctMax;
	double unghiTemp, unghiMax = -1;
	
	for (i=0;i<N;i++)
		if (!puncte[i].vizitat)
		{
			unghiTemp = Unghi(C,puncte[i]);
			if (unghiTemp > unghiMax) 
				{
					unghiMax = unghiTemp;
					punctMax = puncte[i];
					iTemp = i;
				}
		}
	P = C;
	puncte[iTemp].vizitat = true;
	return punctMax;
}

punct PunctInitial()
{
	int i;
	punct punctStart = puncte[0];
	for (i=1;i<N;i++)
	{
		if (puncte[i].x > punctStart.x)
			punctStart = puncte[i];
		if (puncte[i].x == punctStart.x && puncte[i].y < punctStart.y)
			punctStart = puncte[i];
	}
	
	return punctStart; 
}

int main()
{
	Citire();
	int nrSol = 0;
	punct punctInitial = PunctInitial();
	P = punctInitial;
	P.y ++;
	sol[nrSol++] = punctInitial;
	punct punctMobil = PunctUrmator(punctInitial);
	sol[nrSol++] = punctMobil;
	P = punctInitial;
	
	do 
	{
		punctMobil = PunctUrmator(punctMobil);
		sol[nrSol++] = punctMobil;
	}
	while (punctMobil.x != punctInitial.x || punctMobil.y != punctInitial.y);
	nrSol--;
	
	freopen("infasuratoare.out", "w", stdout);
	printf ("%d\n",nrSol);
	for (int i=nrSol-1;i>=0;i--)
		printf("%.6lf %.6lf\n",sol[i].x,sol[i].y);
	return 0;
}