Cod sursa(job #3301047)

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

#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

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

struct Point_t {
	double x;
	double y;
};

Point_t points[MAX_SIZE];	// punctele de intrare
Point_t hull[MAX_SIZE]; // infasuratoarea convexa

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

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

	// Sortare puncte
	qsort(points, N, sizeof(Point_t), Compare);

	// Construirea infasuratoarei convexe
	int hullSize = 0;

	for (int i = 0; i < N; i++) {
		while (hullSize >= 2 && CrossProduct(hull[hullSize - 2], hull[hullSize - 1], points[i]) <= 0) {	// verificare orientare
			hullSize--;
		}
		hull[hullSize++] = points[i];
	}
	for (int i = N - 2, t = hullSize + 1; i >= 0; i--) {
		while (hullSize >= t && CrossProduct(hull[hullSize - 2], hull[hullSize - 1], points[i]) <= 0) {	// verificare orientare
			hullSize--;
		}
		hull[hullSize++] = points[i];
	}

	// Eliminarea ultimului punct adaugat, care este egal cu primul
	hullSize--;

	// Scrierea rezultatului
	fout << hullSize << endl;
	for (int i = 0; i < hullSize; i++) {
		fout << hull[i].x << " " << hull[i].y << endl;
	}

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

    return 0;
}