Cod sursa(job #2157396)

Utilizator AndreiBadescuBadescu Andrei-Octavian AndreiBadescu Data 9 martie 2018 16:41:41
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

#define N 119999

using namespace std;

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

struct plan
{
	double x,y;
};

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

inline double dist ( plan a, plan b )
{
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

inline int orientation ( plan a, plan b, plan c )
{
	int 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 if ( r1 == r2 )
		return 0;

	else
		return 1;
}

bool cmp ( plan b, plan a )
{
	int o;

	o = orientation( bot, a, b );

	switch (o)
	{
		case -1 :
			return 0;

		case 0 :
			return dist( bot, a ) > dist( bot, b );

		case 1 :
			return 1;
	}
}

inline void print ( int n );

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

	int i,h;

	fin >> n >> bot.x >> bot.y;

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

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

	sort ( v, v + n, cmp );

	//print (n);

	/*--n;
	for ( i = 0; i < n; ++i )
	{
		while ( !orientation( bot, v[i], v[i + 1] ) )
			++i;

		v[m++] = v[i];
	}
	*/

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

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

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

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

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