Pagini recente » Cod sursa (job #1638110) | Cod sursa (job #1072949) | Cod sursa (job #265571) | Cod sursa (job #2585589) | Cod sursa (job #2159870)
#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;
}