Cod sursa(job #1355249)

Utilizator ArkinyStoica Alex Arkiny Data 22 februarie 2015 15:45:51
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<iostream>
#include<fstream>
#include<iomanip>
#include<math.h>
#include<algorithm>
using namespace std;

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

int N;

#define MAX 120001

struct Point2D
{
	double x,y,angle;
}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);
}

struct compare
{
	bool operator() (Point2D p1,Point2D p2)
	{
		return p1.angle<p2.angle;
	}
}comp;

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;


	for(int i =0;i<N;i++)
		if(i!=p)
		{
			P[i].angle=atan2(P[i].y-P[p].y,P[i].x-P[p].x)*180/3.14159265;
			if(P[i].angle<0)
				P[i].angle = abs(P[i].angle) +180; 

		}
		else
			P[i].angle=-1000;

	sort(P,P+N,comp);

	R[0]=0;
	R[1]=1;
	int t=2;
	for(int i=2;i<N;i++)
	{
		while(t>=2 && crossProd2D(P[R[t-2]],P[R[t-1]],P[i])<0)
			t--;
		R[t++]=i;

	}
	out<<t<<'\n';
	out<<setprecision(5)<<fixed;
	for(int i=0;i<t;i++)
		out<<P[R[i]].x<<" "<<P[R[i]].y<<'\n';
	
	
	return 0;
}