Cod sursa(job #508691)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 9 decembrie 2010 13:45:25
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#define  nmax 100005 
#include <cmath>
#include <cstdio>


using namespace std;

int sol[nmax],last,k,move,signe;
double mx;

struct pct
{
	double x, y;
}P[nmax];
	

struct cmp
{
	bool operator()(const pct &a,const pct &b)
	{
		if(a.y<b.y)
			return 1;
		if(a.y==b.y)
			if(a.x<b.x)
				return 1;
		return 0;
	}
};

double calc_angle(pct a, pct b)
{
	double xnew=abs(a.x-b.x);
	double ynew=abs(a.y-b.y);
	double result=atan2(ynew,xnew)*180/3.14159265;
	return result;
}


int i,n;

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%lf %lf",&P[i].x,&P[i].y);
	sort(P+1,P+n+1,cmp());
	
	int inc=1;
	last=inc;
	move=1;
	signe=1;
	while(move || last!=inc)
	{	
		inc=last;
		move=0;
		mx=0;
		for(i=inc+signe;i<=n;i+signe)
			if(i!=inc)
				if(calc_angle(P[i],P[last])>mx)
				{
					mx=calc_angle(P[i],P[last]);
					last=i;
					move=1;
				}
		if(last==n)
			signe=-1;
		sol[++k]=last;
	}
	

/*
	#include <stdio.h>
	#include <math.h>

	#define PI 3.14159265

	int main ()
	{
		double x, y, result;
		x = -10.0;
		y = 10.0;
		result = atan2 (y,x) * 180 / PI;
		printf ("The arc tangent for (x=%lf, y=%lf) is %lf degrees\n", x, y, result );
		return 0;
	}
*/ 
	
	return 0;
}