Cod sursa(job #3159110)

Utilizator laurentiu.maticaMatica Laurentiu-Andrei laurentiu.matica Data 20 octombrie 2023 18:48:21
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 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(pair<float,float>x,pair<float,float>x1,pair<int,int>x2)
{
	double det=x.first*x1.second+x1.first*x2.second+x2.first*x1.second-x.first*x2.second-x2.first*x1.second-x1.first*x.second;
	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;
	int k=0;
	while (k < x.size() - 2)
	{
		if (calcOrientare(x[k], x[k + 2], x[k + 1]) == 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], y[k + 2], y[k + 1]) == TRIGONOMETRIC)
			y.erase(y.begin() + k + 1);
		else
			k++;

	}
	cout << x.size() + y.size() - 1 << '\n';
	for (int i = y.size()-1; i > 0; i--)
		cout << y[i].first << ' ' << y[i].second << '\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;
}