Cod sursa(job #2563695)

Utilizator MarcGrecMarc Grec MarcGrec Data 1 martie 2020 13:37:07
Problema Infasuratoare convexa Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#define MAX_N 120000

//#define x first
//#define y second

#include <fstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <utility>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct punct
{
	double x, y;
	
	bool operator< (const punct& other) const
	{
		if (y < other.y) { return true; }
		
		return x < other.x;
	}
} A[MAX_N + 1];

//pair<double, double> A[MAX_N + 1];

//typedef pair<double, double> punct;

int n, top, Stk[MAX_N + 1];

double ArieCuSemn(const punct& a, const punct& b, const punct& c);

int main()
{
	fin >> n;
	int indice = -1;
	for (int i = 1; i <= n; ++i)
	{
		fin >> A[i].x >> A[i].y;
		
		if ((indice == -1) || (A[i] < A[indice]))
		{
			indice = i;
		}
	}
	
	swap(A[1], A[indice]);
	sort(A + 2, A + n + 1, [] (const punct& p1, const punct& p2) { return ArieCuSemn(A[1], p1, p2) >= 0.0; });
	
	Stk[1] = 1;
	Stk[2] = 2;
	top = 2;
	for (int i = 3; i <= n; ++i)
	{
		while ((top >= 2) && (ArieCuSemn(A[Stk[top - 1]], A[Stk[top]], A[i]) < 0.0))
		{
			--top;
		}
		
		Stk[++top] = i;
	}
	
	fout << top << '\n';
	for (int i = 1; i <= top; ++i)
	{
		fout << fixed << setprecision(/*numeric_limits<double>::digits10 + 1*/7) << A[Stk[i]].x << ' ' << A[Stk[i]].y << '\n';
	}
	
	fin.close();
	fout.close();
	return 0;
}

double ArieCuSemn(const punct& a, const punct& b, const punct& c)
{
	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}