Cod sursa(job #2080229)

Utilizator ice_creamIce Cream ice_cream Data 2 decembrie 2017 16:58:27
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int NMAX = 120000;

int n, top;
pair <double, double> puncte[NMAX + 1];
int stiva[NMAX + 1];
bool in_stiva[NMAX + 1];

void citeste() {
	f >> n;
	for (int i = 1; i <= n; i++) {
		f >> puncte[i].first >> puncte[i].second;
	}
}

bool semn(pair <double, double> p1, pair <double, double> p2, pair <double, double> p3) {
	double det = 0;
	det += p1.first * p2.second;
	det += p2.first * p3.second;
	det += p3.first * p1.second;
	det -= p2.second * p3.first;
	det -= p3.second * p1.first;
	det -= p1.second * p2.first;
	return det < 0;
}

void rezolva() {
	sort(puncte + 1, puncte + n + 1);

	top = 2;
	stiva[1] = 1;
	stiva[2] = 2;

	in_stiva[2] = true;

	int pas = 1;
	for (int i = 3; i >= 1; i += pas) {
		if (i == n) pas = -1;
		if (in_stiva[i]) continue;
		while (top >= 2 && semn(puncte[stiva[top - 1]], puncte[stiva[top]], puncte[i])) {
			in_stiva[stiva[top]] = false;
			top--;
		}

		stiva[++top] = i;
		in_stiva[i] = true;
	}
}

void scrie() {
	g << top - 1 << '\n';
	for (int i = 1; i < top; i++) {
		g << fixed << setprecision(6) << puncte[stiva[i]].first << ' ' << puncte[stiva[i]].second << '\n';
	}
}

int main() {
	citeste();
	rezolva();
	scrie();
}