Cod sursa(job #1113279)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 20 februarie 2014 15:24:41
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>

struct COORD{ long double x,y; };


inline long double mycrossproduct(const COORD &p1, const COORD &p2, const COORD &p3){
	return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
}

COORD primul_punct;
inline bool comp_unghi(const COORD &a, const COORD &b){
	return mycrossproduct(primul_punct,a,b)>0;
}

int main(){
	std::ifstream fin("infasuratoare.in");
	std::ofstream fout("infasuratoare.out");

	unsigned n; fin>>n;

	std::vector<COORD> puncte(n);
	for(unsigned i=0;i<n;++i) fin>>puncte[i].x>>puncte[i].y;

	primul_punct=puncte[0];
	for(unsigned i=1;i<n;++i)
		if(puncte[i].y<primul_punct.y || ((puncte[i].y==primul_punct.y)&&(puncte[i].x<primul_punct.x)))
			primul_punct=puncte[i];

	std::sort(puncte.begin(),puncte.end(),comp_unghi);

	std::vector<COORD> st(n);
	st[0]=puncte[0]; st[1]=puncte[1];
	unsigned top=1;

	for(unsigned i=2;i<n;++i){
		while(top>0 && mycrossproduct(st[top-1],st[top],puncte[i])<0) --top;
		st[++top]=puncte[i];
	}

	fout<<std::fixed<<std::setprecision(6);
	fout<<(top+1)<<"\n";
	for(unsigned i=0;i<=top;++i) fout<<st[i].x<<" "<<st[i].y<<"\n";

	fout.close();
}