Cod sursa(job #2157979)

Utilizator AndreiBadescuBadescu Andrei-Octavian AndreiBadescu Data 10 martie 2018 08:23:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

#define N 120000

using namespace std;

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

struct plan
{
	double x,y;
};

int n;
plan sv[N], v[N];

inline int orientation ( plan a, plan b, plan c )
{
	double r1, r2;

	r1 = (b.x - a.x) * (c.y - b.y);
	r2 = (c.x - b.x) * (b.y - a.y);

	if ( r1 > r2 )
		return 1;
	else
		return 0;
}

bool cmp ( plan b, plan a )
{
	return orientation( v[0], a, b );
}

void print ();

int main()
{
	ios::sync_with_stdio (false);

	int i, h, pos = 0;

	fin >> n >> v[0].x >> v[0].y;

	for ( i = 1; i < n; ++i )
	{
		fin >> v[i].x >> v[i].y;

		if ( v[i].y < v[pos].y )
			pos = i;
		else if ( v[i].y == v[pos].y && v[i].x < v[pos].x )
			pos = i;
	}

	swap ( v[0], v[pos] );

	sort ( v + 1, v + n, cmp );

	//print();

	sv[0] = v[0], sv[1] = v[1];
	h = 1;
	for ( i = 2; i < n; ++i )
	{
		while ( orientation( sv[h - 1], sv[h], v[i] ) == 1 && h > 1 )
			--h;

		sv[++h] = v[i];
	}

	fout << h + 1 << '\n';

	fout << fixed << setprecision (12) << sv[0].x << " " << sv[0].y << '\n';
	for ( ; h > 0; --h )
		fout << fixed << setprecision (12) << sv[h].x << " " << sv[h].y << '\n';
}

void print ()
{
	for ( int i = 0; i < n; ++i )
		fout << fixed << setprecision (12) << v[i].x << " " << v[i].y << '\n';
	fout << '\n';
}