Cod sursa(job #1266139)

Utilizator vladrochianVlad Rochian vladrochian Data 18 noiembrie 2014 12:52:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;

const int kMaxN = 120005;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int N;
struct Point {
	double x, y;
} p[kMaxN];
vector<int> ch;

double Area(const Point &p1, const Point &p2, const Point &p3) {
	return p1.x * p2.y - p1.y * p2.x +
	       p2.x * p3.y - p2.y * p3.x +
	       p3.x * p1.y - p3.y * p1.x;
}
bool Compare(const Point &p1, const Point &p2) {
	return Area(p[0], p1, p2) > 0;
}

int main() {
	fin >> N;
	for (int i = 0; i < N; ++i) {
		fin >> p[i].x >> p[i].y;
		if (p[i].x < p[0].x)
			swap(p[0], p[i]);
	}
	sort(p + 1, p + N, Compare);
	ch.push_back(0);
	for (int i = 1; i < N; ++i) {
		while (ch.size() > 1 && Area(p[ch[ch.size() - 2]], p[ch[ch.size() - 1]], p[i]) <= 0)
			ch.pop_back();
		ch.push_back(i);
	}
	fout << ch.size() << "\n" << setprecision(12) << fixed;
	for (int i : ch)
		fout << p[i].x << " " << p[i].y << "\n";
	return 0;
}