Cod sursa(job #518744)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 2 ianuarie 2011 22:52:33
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<fstream>
#include<algorithm>
using namespace std;

#define NMAX 120010

const char infile[]="infasuratoare.in";
const char outfile[]="infasuratoare.out";

struct punct
{
	double x;
	double y;
};

int S[NMAX];
int k=0;

int N;
int C;

punct Start;
punct A[NMAX];

inline double produs(punct a,punct b,punct c)
{
	return ((b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y));
}

void citire()
{
	fstream fin(infile,ios::in);
	fin>>N;
	int indice;
	double min=1000000010;
	for(int i=1;i<=N;i++)
	{
		fin>>A[i].x>>A[i].y;
		if(A[i].x<min)
		{
			min=A[i].x;
			indice=i;
		}
		else if(A[i].x==min && A[i].y<A[indice].y)
		{
			min=A[i].x;
			indice=i;
		}
	}
	Start.x=A[indice].x;
	Start.y=A[indice].y;
	swap(A[1],A[indice]);
	fin.close();
}

bool f(punct a,punct b)
{
	double x,y;
	x=(a.y-Start.y)/(a.x-Start.x);
	y=(b.y-Start.y)/(b.x-Start.x);

	return x<y;
}

void afisare()
{
	fstream fout(outfile,ios::out);
	fout<<k<<"\n";
	for(int i=1;i<=k;i++)
		fout<<A[S[i]].x<<" "<<A[S[i]].y<<"\n";
	fout.close();
}

void Graham()
{
	double x;
	k++;
	S[k]=1;
	k++;
	S[k]=2;
	for(int i=3;i<=N;i++)
	{
		x=produs(A[S[k-1]],A[S[k]],A[i]);
		if(x<0)
		{
			S[k]=i;
		}
		else
		{
			k++;
			S[k]=i;
		}
	}
	
}

int main()
{
	citire();
	sort(A+2,A+N+1,f);
	Graham();
	afisare();
}