Cod sursa(job #2739032)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 6 aprilie 2021 18:27:17
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 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[120001];

long double det (punct a, punct b, punct c)
{
	//sfantul xY - Xy!
	return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}

bool comp (const punct &a, const punct &b)
{
	return det (p[1], a, b) > 0;
}

int s[120001];

int main()
{
	int n, i, ind = 1;
	fin >> n;
	for (i = 1; i<=n; i++)
	{
		fin >> p[i].x >> p[i].y;
		if (p[i].y < p[ind].y || (p[i].y == p[ind].y && p[i].x < p[ind].x))
			ind = i;
	}
	swap(p[1], p[ind]);
	sort(p+2, 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(18);
	for (i = s[0]; i>=1; i--)
		fout << p[s[i]].x << ' ' << p[s[i]].y << '\n';
	return 0;
}