Cod sursa(job #3301064)

Utilizator sonia.peiovPeiov Sonia sonia.peiov Data 21 iunie 2025 14:00:01
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.88 kb
// https://infoarena.ro/problema/infasuratoare

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

struct Point_t {
	double x;
	double y;

	bool operator<(const Point_t& other) const {	// operator de comparare pentru sortare: sortam punctele de la stanga la dreapta, de jos in sus
		if (x != other.x) {
			return x < other.x;
		}			
		return y < other.y;
	}
};

// Functie pentru a verifica daca doua puncte sunt egale
bool isEqual(const Point_t& a, const Point_t& b) {
	return (a.x == b.x && a.y == b.y);
}

// Functia pentru calcularea produsului vectorial -> folosita pentru a verifica orientarea punctelor (unghi stanga sau dreapta)
// > 0 : c e la stanga lui a -> b
// = 0 : c e colinear cu a si b
// < 0 : c e la dreapta lui a -> b
double CrossProduct(const Point_t& a, const Point_t& b, const Point_t& c) {
	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

// Functie care construieste infasuratoarea convexa a multimii de pncte date
vector<Point_t> ConvexHull(const vector<Point_t>& points) {

	vector<Point_t> hull;	// infasuratoarea
	vector<Point_t> lower, upper;	// jumatatile inferioara si superioara ale infasuratoarei

	int n = points.size();

	if (n < 3) return hull;	// daca avem mai putin de 3 puncte, nu putem forma un poligon

	for (int i = 0; i < n; i++) {
		while (lower.size() >= 2 && CrossProduct(lower[lower.size() - 2], lower.back(), points[i]) <= 0) {
			lower.pop_back();	// eliminam ultimul punct daca nu formeaza un unghi stang
		}
		lower.push_back(points[i]);
	}

	for (int i = n - 1; i >= 0; i--) {
		while (upper.size() >= 2 && CrossProduct(upper[upper.size() - 2], upper.back(), points[i]) <= 0) {
			upper.pop_back();	// eliminam ultimul punct daca nu formeaza un unghi stang
		}
		upper.push_back(points[i]);
	}

	// Eliminam ultimul punct din fiecare jumatate, deoarece ele sunt egale cu primul punct din cealalta jumatate
	lower.pop_back();
	upper.pop_back();

	// Combinam cele doua jumatati pentru a forma infasuratoarea completa
	hull = lower;
	hull.insert(hull.end(), upper.begin(), upper.end());

	return hull;
}

int main() {

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

	int N;
	fin >> N;

	vector<Point_t> points(N);	// punctele de intrare

	for (int i = 0; i < N; i++) {
		fin >> points[i].x >> points[i].y;
	}

	sort(points.begin(), points.end());	// sortam punctele conform operatorului < definit

	points.erase(unique(points.begin(), points.end(), isEqual), points.end());	// eliminam punctele duplicate

	vector<Point_t> hull = ConvexHull(points);

	// Afisarea rezultatului
	fout << hull.size() << endl;
	fout << setprecision(6) << fixed;
	for (int i = 0; i < (int)hull.size(); i++) {
		fout << hull[i].x << " " << hull[i].y << endl;
	}

	fin.close();
	fout.close();

    return 0;
}