Cod sursa(job #1354065)

Utilizator ArkinyStoica Alex Arkiny Data 21 februarie 2015 16:42:21
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<iostream>
#include<fstream>
#include<math.h>
#include<iomanip>
using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

int N;

#define MAX 120001

struct Point2D
{
	double x,y;
}P[MAX];

int R[MAX];


double crossProd2D(Point2D p1,Point2D p2,Point2D p3)
{
	return (p3.y-p2.y)*(p2.x-p1.x) - (p2.y-p1.y)*(p3.x-p2.x);
}
double slope(Point2D p1,Point2D p2)
{
	return (p2.y-p1.y)/(p2.x-p1.x);
}
double dist(Point2D p1,Point2D p2)
{
	return sqrt((p2.y-p1.y)*(p2.y-p1.y) + (p2.x-p1.x)*(p2.x-p1.x));
}
int main()
{
	in>>N;
	int i;
	for(i=0;i<N;i++)
		in>>P[i].x>>P[i].y;

	int p=0;
	double min=P[0].y;
    for(i=1;i<N;i++)
		if(P[i].y<min)
		{
			min=P[i].y;
			p=i;
		}
		else if(P[i].y==min)
			if(P[i].x<P[p].x)
				p=i;

	R[0]=p;

	int q,s=p;
	int nr=0;
	i=0;
	R[0]=p;
	do
	{
      q=(s+1)%N;
	  for(int i=0;i<N;i++)
		  if(crossProd2D(P[s],P[q],P[i])<0)
	           q=i;
		  else if(crossProd2D(P[s],P[q],P[i])==0)
			  if(P[i].y<P[s].y)
				  q=i;

	  R[i+1]=q;
	  s=q;
	  nr++;
	  i++;
	}while(s!=p);
	out<<nr<<'\n';
	out<<setprecision(6)<<fixed;
	for(int i=0;i<nr;i++)
		out<<P[R[i]].x<<" "<<P[R[i]].y<<'\n';
	
	return 0;
}