Cod sursa(job #2714399)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 1 martie 2021 19:26:17
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

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

struct punct
{
	long double x, y;
} p[120000];

long double det (punct a, punct b, punct c)
{
	return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

bool comp (punct a, punct b) //verifica daca b fata de a este in sens antitrigonometric <=> unghiul polar al lui b este mai mare decat unghiul polar al lui a
{
	return det (p[1], a, b) < 0;
}

int s[120000];

int main()
{
	int n, i, imin = 1;
	fin >> n;
	for (i = 1; i<=n; i++)
	{
		fin >> p[i].x >> p[i].y;
		if (p[i].y < p[imin].y)
			imin = i;
		else if (p[i].y == p[imin].y && p[i].x < p[imin].x)
			imin = i;
	}
	swap(p[1], p[imin]);
	sort(p+1, p+n+1, comp);
	s[0] = 2;
	s[1] = 1;
	s[2] = 2;
	for (i = 3; i<=n; i++)
	{
		while (s[0] >= 2 && det (p[s[s[0]-1]], p[s[s[0]]], p[i]) >= 0)
			s[0]--;
		s[++s[0]] = i;
	}
	fout << s[0] << '\n';
	fout << fixed << setprecision(15);
	for (i = s[0]; i>=1; i--)
		fout << p[s[i]].x << ' ' << p[s[i]].y << '\n';
	return 0;
}