Cod sursa(job #3318857)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 29 octombrie 2025 14:10:26
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdint.h>
#include <algorithm>

const int32_t MAX_N = 120000;

struct Point {
	double x, y;
};

Point vec[MAX_N];
int32_t res[MAX_N], top = 0;

double SignedArea(const Point& p1, const Point& p2, const Point& p3) {
	return 0.5 * (p1.x * p2.y + p2.x * p3.y + p3.y * p1.x - p1.y * p2.x - p2.y * p3.x - p3.y * p1.x);
}
bool CompPoints(const Point& p1, const Point& p2) {
	return SignedArea(vec[0], p1, p2) > 0.0;
}

int main() {
	std::ifstream fin("infasuratoare.in");
	std::ofstream fout("infasuratoare.out");

	int32_t n;
	fin >> n;
	for(int32_t i = 0; i != n; ++i)
		fin >> vec[i].x >> vec[i].y;
	
	for(int32_t i = 1; i != n; ++i) {
		if(vec[i].x < vec[0].x || (vec[i].x == vec[0].x && vec[i].y < vec[0].y))
			std::swap(vec[i], vec[0]);
	}
	std::sort(vec + 1, vec + n, CompPoints);

	res[0] = 0;
	res[1] = 1;
	top = 2;

	for(int32_t i = 2; i != n; ++i) {
		while(top >= 2 && SignedArea(vec[res[top - 2]], vec[res[top - 1]], vec[i]) < 0.0)
			--top;
		res[top++] = i;
	}
	
	fout << std::fixed << std::setprecision(6);
	fout << top << '\n';
	for(int32_t i = 0; i != top; ++i)
		fout << vec[res[i]].x << ' ' << vec[res[i]].y << '\n';

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

	return 0;
}