Cod sursa(job #944027)

Utilizator MciprianMMciprianM MciprianM Data 27 aprilie 2013 10:34:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<double, double> pdd;
typedef vector<pdd> vdd;

pdd leftDown;

pdd operator-(const pdd& a, const pdd& b) {
	return pdd(a.first - b.first, a.second - b.second);
}

double operator*(const pdd& a, const pdd& b) {
	return (a.first * b.second - a.second * b.first);
}

bool cmp(const pdd& a, const pdd& b) {
	return ((a - leftDown) * (b - leftDown)) > 0;
}

void solve(vdd& v, vdd& ans) {
	int pos = 0, l = v.size();
	for(int i = 1; i < l; i++)
		if(v[i] < v[pos])	pos = i;
	swap(v[pos], v[0]);
	leftDown = v[pos];
	sort(v.begin() + 1, v.end(), cmp);
	ans.push_back(v[0]);
	ans.push_back(v[1]);
	for(int i = 2; i < l; i++) {
		while(
			ans.size() > 2 && 
			(ans.back() - ans[ans.size() - 2]) * (v[i] - ans.back()) < 0.0
		)	ans.pop_back();
		ans.push_back(v[i]);
	}
}

int main(){
	int n, h;
	ifstream f("infasuratoare.in");
	f >> n;
	vdd v(n), ans;
	for(int i = 0; i < h; i++)
		f >> v[i].first >> v[i].second;
	f.close();
	solve(v, ans);
	FILE* g = fopen("infasuratoare.out", "wt");
	h = ans.size();
	fprintf(g, "%d\n", h);
	for(int i = 0; i < h; i++)
		fprintf(g, "%.6lf %.6lf\n", ans[i].first, ans[i].second);
	fclose(g);
	return 0;
}