Cod sursa(job #2592103)

Utilizator blackmanta45Andrei blackmanta45 Data 1 aprilie 2020 06:41:01
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <iterator>
#include <list>
#define inf 2e9
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int i, poz, h, n;
double xc, yc;
pair <double, double> start;
vector<pair<double,double>> v;
list<int> s;
double calc(pair<double, double> a, pair <double, double> b, pair <double, double> c) {
	return (b.x - c.x) * (a.y - c.y) - (b.y - c.y) * (a.x - c.x);
}

bool cmp(pair<double, double> a, pair <double, double> b) {
	if (calc(a, b, start) < 0)
		return 1;
	return 0;
}

int main() {
	fin >> n;
	start = { inf,inf };
	for (i = 0; i < n; i++) {
		fin >> xc >> yc;
		v.push_back(make_pair(xc, yc));
		if (xc < start.x)
			start = v[i], poz = i;
		else
			if (v[i].x == start.x && v[i].y < start.y)
				start = v[i], poz = i;
	}

	swap(v[0], v[poz]);
	sort(v.begin(),v.end(), cmp);
	s.push_back(0);
	s.push_back(1);
	for (i = 2; i < n; i++) {
		if (calc(v[s.back()], v[i], v[*next(s.rbegin())]) <= 0)
			s.push_back(i);
		else {
			while (calc(v[s.back()], v[i], v[*next(s.rbegin())]) > 0)
				s.pop_back();
			s.push_back(i);
		}
	}
	fout << s.size() << "\n";
	for (auto it:s)
		fout << setprecision(6) << fixed << v[it].x << " " << v[it].y << "\n";
}