Cod sursa(job #2462811)

Utilizator gabib97Gabriel Boroghina gabib97 Data 27 septembrie 2019 20:36:06
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>
#define N 120005

using namespace std;

struct point {
	double x, y;
} p[N];
vector<int> selectedPoints;
int n;

double det(const point &o, const point &a, const point &b) {
	return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}

double dist(const point &a, const point b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

void convex_hull() {
	selectedPoints.push_back(0);
	selectedPoints.push_back(1);

	int t = 1;
	for (int i = 2; i < n; i++) {
		double d = det(p[selectedPoints[t - 1]], p[selectedPoints[t]], p[i]);
		if (d > 0)
		  	selectedPoints.push_back(i), t++;
		else if (d == 0)
			*selectedPoints.rbegin() = i;
		else {
			while (d < 0) {
				selectedPoints.pop_back();
				t--;
				d = det(p[selectedPoints[t - 1]], p[selectedPoints[t]], p[i]);
			}
			selectedPoints.push_back(i);
			t++;
		}
	}
}

int main() {
	ifstream cin ( "infasuratoare.in");
	ofstream cout ("infasuratoare.out");
	cin >> n;
	double xMin = DBL_MAX, yMin = DBL_MAX;
    int refPoint;
	for (int i = 0; i < n; i++) {
		cin >> p[i].x >> p[i].y;
		if (p[i].y < yMin || (p[i].y == yMin && p[i].x < xMin))
			xMin = p[i].x, yMin = p[i].y, refPoint = i;
	}

	swap(p[refPoint], p[0]);
	sort(p + 1, p + n, [](const point &a, const point &b) {
		double d = det(p[0], a, b);
		return d > 0 || (d == 0 && dist(p[0], a) < dist(p[0], b));
	});

	convex_hull();
	cout << selectedPoints.size();
	for (int i : selectedPoints)
		cout << fixed << setprecision(6) << '\n' << p[i].x << " " << p[i].y;
	return 0;
}