Cod sursa(job #3221439)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 7 aprilie 2024 10:41:10
Problema Infasuratoare convexa Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdint.h>
#include <algorithm>

const int32_t MAX_N = 120000;

struct Pos {
	double x;
	double y;
};

Pos vec[MAX_N];
int32_t res[MAX_N], top;

double Area(const Pos& pos1, const Pos& pos2, const Pos& pos3) {
	return (pos1.x * pos2.y + pos2.x * pos3.y + pos3.x * pos1.y) - (pos1.y * pos2.x + pos2.y * pos3.x + pos3.y * pos1.x);
}
bool Compare(const Pos& pos1, const Pos& pos2) {
	return Area(vec[0], pos1, pos2) > 0;
}

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

	int32_t n;
	fin >> n;
	for(int32_t i = 0; i != n; ++i)
		fin >> vec[i].x >> vec[i].y;
	
	int32_t minPos = 0;
	for(int32_t i = 1; i != n; ++i)
		if(vec[i].x < vec[minPos].x || (vec[i].x == vec[minPos].x && vec[i].y < vec[minPos].y))
			minPos = i;

	std::swap(vec[0], vec[minPos]);
	std::sort(vec + 1, vec + n, Compare);

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

	for(int32_t i = 0; i != n; ++i) {
		for(; top != 1 && Area(vec[res[top - 2]], vec[res[top - 1]], vec[i]) <= 0; --top);
		res[top++] = i;
	}

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