Cod sursa(job #2159870)

Utilizator AndreiBadescuBadescu Andrei-Octavian AndreiBadescu Data 11 martie 2018 10:53:52
Problema Suma si numarul divizorilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>

typedef unsigned long long ull;
using namespace std;

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

int n,i,j,ma,m,h;
ull r;

struct plan
{
	int x,y;
};

plan p,g,bot,sv[100000];
vector <plan> v;

int orientation ( plan a, plan b, plan c )
{
	int d1 = (b.x - a.x) * (c.y - b.y),
	    d2 = (b.y - a.y) * (c.x - b.x);

	if ( d1 > d2 )
		return 1;
	else if ( d1 < d2 )
		return -1;
	else
		return 0;
}

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

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

	if ( o == 1 )
		return 1;
	else if ( o == -1 )
		return 0;
	else
		return dist (bot, a) < dist (bot, b);
}

int main()
{
	fin >> n >> bot.x >> bot.y;

	for ( i=0, --n; i<n; i++ )
	{
		fin >> p.x >> p.y;

		/// finding bottom-most point
		if ( p.y < bot.y || (p.y == bot.y && p.x < bot.x) )
			swap (bot, p);

		v.push_back (p);
	}

	/// sorting by polar angle
	sort (v.begin(), v.end(), cmp);

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

		v[m++] = v[i];
	}
	v[m++] = v[n];

	if ( m < 2 )
	{
		fout << fixed << setprecision(6) << sqrt( dist(bot,v[0]) );
		return 0;
	}

	sv[0] = bot, sv[1] = v[0], sv[2] = v[1];

	for ( i=h=2; i<m; i++ )
	{
		while ( orientation (sv[h-1], sv[h], v[i] ) != 1 )
			--h;

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

	for ( i=0; i<h; i++ )
		for ( j=i+1; j<=h; j++ )
			ma = max ( ma, dist (sv[i],sv[j]) );

	fout << fixed << setprecision(6) << sqrt(ma);

	return 0;
}