Cod sursa(job #3301053)

Utilizator sonia.peiovPeiov Sonia sonia.peiov Data 21 iunie 2025 12:59:34
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.35 kb
// https://infoarena.ro/problema/infasuratoare

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

using namespace std;

#define MAX_SIZE 120001	// numarul maxim de puncte + 1

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 de comparare pentru qsort
int Compare(const void* a, const void* b) {	// sortam punctele de la stanga la dreapta, de jos in sus
	Point_t* pointA = (Point_t*)a;
	Point_t* pointB = (Point_t*)b;
	if (pointA->x < pointB->x) return -1;
	if (pointA->x > pointB->x) return 1;
	if (pointA->y < pointB->y) return -1;
	if (pointA->y > pointB->y) return 1;
	return 0;
}

// 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(MAX_SIZE);	// punctele de intrare

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

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

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

	for (int i = 0; i < N; i++) {
		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
	}
	
	// Afisam rezultatul
	fout << hull.size() << "\n";	// afisam numarul de puncte din infasuratoare
	for (int i = 0; i < hull.size(); i++) {
		fout << hull[i].x << " " << hull[i].y << "\n";	// afisam coordonatele punctelor din infasuratoare
	}

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

    return 0;
}