Cod sursa(job #3159140)

Utilizator laurentiu.maticaMatica Laurentiu-Andrei laurentiu.matica Data 20 octombrie 2023 19:33:42
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
vector<pair<float, float>>x;
bool valid(pair<float, float>a, pair<float, float>b)
{
	if (a.first < b.first)
		return true;
	else if (a.first > b.first)
		return false;
	else if (a.second < b.second)
		return true;
	else return false;
}
enum Orientare {
	TRIGONOMETRIC,
	ORAR,
	COLIN
};
Orientare calcOrientare(float x1, float y1, float x2, float y2, float x3, float y3)
{
	double det = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
	if (det > 0)
		return TRIGONOMETRIC;
	else if (det < 0)
		return ORAR;
	else
		return COLIN;
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		pair<float, float>p;
		cin >> p.first >> p.second;
		x.push_back(p);
	}
	sort(x.begin(), x.end(), valid);
	vector<pair<float, float>>y=x;
	int k = 0;
	//y.push_back(x[0]);
	while (k < x.size() - 2)
	{
		if (calcOrientare(x[k].first, x[k].second, x[k + 2].first, x[k + 2].second, x[k + 1].first, x[k + 1].second) == ORAR)
		{
			//y.push_back(x[k + 1]);
			x.erase(x.begin() + k + 1);
		}
		else
			k++;
	}
	k = 0;
	while (k < y.size() - 2)
	{
		if (calcOrientare(y[k].first, y[k].second, y[k + 2].first, y[k + 2].second, y[k + 1].first, y[k + 1].second) == TRIGONOMETRIC)
			y.erase(y.begin() + k + 1);
		else
			k++;

	}
	//y.push_back(x[x.size() - 1]);
	cout << x.size() + y.size() - 2 << '\n';
	for (int i = 1; i <y.size()-1; i++)
		cout << y[i].first << ' ' << y[i].second << '\n';
	cout << '\n' << '\n';
	for (int i = x.size()-1; i >= 0; i--)
		cout << x[i].first << ' ' << x[i].second << '\n';
	/*for (int i = 0; i < n; i++, cout << '\n')
	{
		cout << x[i].first << ' ' << x[i].second;
	}*/
	return 0;
}