Cod sursa(job #2579707)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 12 martie 2020 18:54:02
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.12 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

const long double eps = 1e-12;

struct Punct
{
	long double x, y;
	Punct(long double abscisa, long double ordonata) : x(abscisa), y(ordonata) {}
	Punct() {}
	// se vor compara puncte, deci trebuie sa
	// supraincarcam operatorii de egalitate
	bool operator ==(const Punct& other)
	{
		return (abs(x - other.x) < eps) && (abs(y - other.y) < eps);
	}
	bool operator !=(const Punct& other)
	{
		return (abs(x - other.x) > eps) || (abs(y - other.y)> eps);
	}
};

Punct g;

int Orientare(const Punct& A, const Punct& B, const Punct& C)
{
	long double temp = (B.y - A.y) * (C.x - A.x) - (C.y - A.y) * (B.x - A.x);
	if (temp < 0)
		return -1;
	else if (temp < eps)
		return 0;
	else
		return 1;
}

void Citire(vector<Punct>& P, int& N)
{
	cin >> N;
	long double x, y;
	for (int i = 1; i <= N; ++i)
	{
		cin >> x >> y;
		P.push_back(Punct(x, y));
	}
}

vector<Punct> Jarvis(const vector<Punct>& P)
{
	int start = 0; // vectorii incep de la 0
	for (int i = 1; i < P.size(); ++i)
		if (P[i].x < P[start].x || (P[i].x == P[start].x && P[i].y > P[start].y))
			start = i;

	vector<Punct> CH;
	
	CH.push_back(P[start]);
	
	for (int i = 0; i < CH.size(); ++i)
	{
		Punct nextPct = (CH[i] == P[0]) ? P[1] : P[0];
		for (int j = 0; j < P.size(); ++j)
			if (Orientare(CH[i], P[j], nextPct) > 0)
				nextPct = P[j];
		if (nextPct != CH[0])
			CH.push_back(nextPct);
	}
	
	return CH;
}

inline bool cmp(Punct a, Punct b)
{
	return atan2(a.y - g.y, a.x - g.x) > atan2(b.y - g.y, b.x - g.x);
}

int main()
{
	int N;
	vector<Punct> P;
	
	Citire(P, N);
	
	vector<Punct> CH = Jarvis(P);
	cout << CH.size() << endl;
	
	for (size_t i = 0; i < CH.size(); ++i)
	{
		g.x += CH[i].x;
		g.y += CH[i].y;
	}

	g.x /= CH.size();
	g.y /= CH.size();
	
	sort(CH.begin(), CH.end(), cmp);
	
	for (size_t i = 0; i < CH.size(); ++i)
		cout << fixed << setprecision(6) << CH[i].x << " " << CH[i].y << "\n";
	
	return 0;
}