Cod sursa(job #1222380)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 22 august 2014 23:49:46
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 120010
#define EPS 1e-10
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct Punct {
	long double X, Y;
	Punct() {
		X = Y = 0;
	}
	Punct(long double X, long double Y) {
		this->X = X;
		this->Y = Y;
	}
} S[MAX];
vector<Punct> Sup, Sinf;
int N;

bool cmp(Punct A, Punct B) {
	return A.X < B.X;
}

long double Det(Punct A, Punct B, Punct C) {
	return A.X*B.Y + B.X*C.Y + C.X*A.Y - B.X*A.Y - C.X*B.Y - A.X*C.Y;
}

void Subsets() {
	Sup.push_back(S[1]);
	Sinf.push_back(S[1]);
	for (int i = 2; i < N; i++) {
		if (Det(S[1], S[N], S[i]) > EPS) {
			Sup.push_back(S[i]);
		} else {
			Sinf.push_back(S[i]);
		}
	}
	Sup.push_back(S[N]);
	Sinf.push_back(S[N]);
}

void UpSubset() {
	int k = 1;
	for (int i = 2; i < Sup.size(); i++) {
		while (k >= 1 && Det(Sup[k-1], Sup[i], Sup[k]) < EPS) k--;
		Sup[++k] = Sup[i];
	}
	Sup.resize(k+1);
}

void InfSubset() {
	int k = 1;
	for (int i = 2; i < Sinf.size(); i++) {
		while (k >= 1 && Det(Sinf[k-1], Sinf[i], Sinf[k]) > EPS) k--;
		Sinf[++k] = Sinf[i];
	}
	Sinf.resize(k+1);
}

int main() {

	f >> N;	
	for (int i = 1; i <= N; i++) {
		f >> S[i].X >> S[i].Y;
	}
	
	sort(S+1, S+N+1, cmp);
	Subsets();
	
	UpSubset();
	InfSubset();
	
	g << setprecision(6) << fixed;

	g << Sup.size() + Sinf.size() - 2 << "\n";
	for (int i = Sup.size() - 1; i >= 0; i--) {
		g << Sup[i].X << " " << Sup[i].Y << "\n";
	}
	for (int i = 1; i < Sinf.size() - 1; i++) {
		g << Sinf[i].X << " " << Sinf[i].Y << "\n";
	}	
	
	return 0;
}