Cod sursa(job #3301056)

Utilizator sonia.peiovPeiov Sonia sonia.peiov Data 21 iunie 2025 13:21:42
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.47 kb
// https://infoarena.ro/problema/infasuratoare

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstdlib>

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;
	}
};

// 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);
}

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

	// Construirea infasuratoarei
	vector<Point_t> hull;	// stiva pentru a construi infasuratoarea

	for (int i = 0; i < N; i++) {	// partea de sus
		while (hull.size() >= 2) {
			if (CrossProduct(hull[hull.size() - 2], hull.back(), points[i]) <= 0) {
				hull.pop_back();	// eliminam ultimul punct daca orientarea nu este stanga
			}
			else {
				break;	// daca orientarea este stanga, iesim din bucla
			}
		}
		hull.push_back(points[i]);	// adaugam punctul curent in infasuratoare
	}

	int M = hull.size();	// numarul de puncte din partea de sus a infasuratoarei
	for (int i = N - 2; i >= 0; i--) {	// partea de jos
		while (hull.size() > M) {
			if (CrossProduct(hull[hull.size() - 2], hull.back(), points[i]) <= 0) {
				hull.pop_back();	// eliminam ultimul punct daca orientarea nu este stanga
			}
			else {
				break;	// daca orientarea este stanga, iesim din bucla
			}
		}
		hull.push_back(points[i]);	// adaugam punctul curent in infasuratoare
	}

	// Afisam rezultatul
	fout << hull.size() - 1 << "\n";	// afisam numarul de puncte din infasuratoare, - 1 pentru ca avem un punct duplicat la final
	for (int i = 1; i < hull.size(); i++) {
		fout << hull[i].x << " " << hull[i].y << "\n";	// afisam coordonatele punctelor, fara primul punct (care este duplicat)
	}

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

    return 0;
}