Cod sursa(job #1876939)

Utilizator eilerGabriel-Ciprian Stanciu eiler Data 12 februarie 2017 19:20:31
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <vector>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

struct point{
	double X, Y;
};

int N;
point q;

double determ(point a, point b, point c){
	return (b.X-a.X)*(c.Y-a.Y)-(b.Y-a.Y)*(c.X-a.X);
}

bool cmp(point a, point b){
	return determ(q, a, b)>0;
}

int main(){
	fstream f;

	f.open("infasuratoare.in", ios_base::in);
	f >> N;
	vector<point> P(N);
	for (int i=0; i<N; i++){
		f >> P[i].X >> P[i].Y;
		if (P[0].Y>P[i].Y || (P[0].Y==P[i].Y && P[0].X>P[i].X))
			swap(P[i], P[0]);
	}
	f.close();

	q=P[0];
	sort(P.begin()+1, P.begin()+N, cmp);
	vector<int> S;
	S.push_back(0); S.push_back(1);
	for (int i=2; i<N; i++){
		while (S.size()>1 && determ(P[*(S.rbegin()+1)], P[S.back()], P[i])<=0)
			S.pop_back();
		S.push_back(i);
	}

	f.open("infasuratoare.out", ios_base::out);
	f << fixed << S.size() << '\n';
	for (unsigned int i=0; i<S.size(); i++)
		f << setprecision(6) << P[S[i]].X << ' ' << P[S[i]].Y << '\n';
	f.close();

	return 0;
}