Cod sursa(job #749897)

Utilizator Theorytheo .c Theory Data 19 mai 2012 15:46:31
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include<fstream>
#include<iomanip>
#define nmax 120004
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct {double x; double y;
	inline void get()
	{
		fin >> x>>y;
	}
	inline void getout()
	{
		fout<< fixed;
		fout<< setprecision(6)<<x << " " <<y <<'\n'; 
	}
};
Punct v[nmax], sol[nmax];
int n, Nr = 2;

bool cmp(Punct A, Punct B)
{
	return (A.y < B.y)|| (A.y == B.y && A.x < B.x);
}
void read()
{
	fin >>n;
	for(int i = 1; i <= n; i++)
		v[i].get();
	sort(v + 1, v + 1 + n,cmp);
}
bool semn(Punct A, Punct B, Punct C)
{
	double a = A.y - B.y;
	double b = B.x - A.x;
	double c = B.y * A.x - B.x * A.y;
	return (a * C.x + b* C.y +c) < 0;
}
void solve()
{
	int i;
	
	sol[1] = v[1];
	sol[2] = v[2];
	for(i = 3; i <= n; ++i)//det partea din stanga a infasuratoarei pana la cel mai inalt punct
	{
		while( Nr >= 2 && semn (sol[Nr - 1], sol[Nr] , v[i]) )//daca punctul e sub dreapta il scot din lista
			Nr--;
		sol[++Nr] = v[i];
		
	}
	
	
	for( i = n-1 ;i >= 1; --i)// det partea din dreapta
	{
		while(Nr >= 2 && semn(sol[Nr - 1] , sol[Nr] , v[i]) )//daca punctul e sub dreapta il scot din lista
			Nr--;
		sol[++Nr] = v[i];
	}
	Nr--;
	
}
int main()
{
	read();
	solve();

	fout<<Nr <<'\n';
	for(int i= 1; i <= Nr; ++i)
		sol[i].getout();
	
	fin.close();
	return 0;
}