先求凸包再枚举包上的点对距离。
#include <cstdio>#include <string>#include <cmath>#include <algorithm>using namespace std;#define eps 1e-10typedef struct
...{
double x, y; int id;
} Point;Point p[30001];int N;int stack[30001];int used[30001];int cmp ( const Point &a, const Point &b )...{ if ( a.y == b.y ) return a.x < b.x; return a.y < b.y;}int init ()...{ if ( scanf ( "%d", &N ) != 1 ) return 0; int i; for ( i = 0; i < N; i ++ ) scanf ( "%lf%lf", &p[i].x, &p[i].y ); sort ( p, p + N, cmp ); for ( i = 0; i < N; i ++ ) p[i].id = i; return 1;}int dCmp ( double x )...{ if ( x < -eps ) return -1; if ( x > eps ) return 1; return 0;}double crossDet ( Point &a, Point &b, Point &c )...{ return dCmp ( ( b.x - a.x ) * ( c.y - a.y ) - ( c.x - a.x ) * ( b.y - a.y ) );}void ps ( int top )...{ int i; for ( i = 0; i <= top; i ++ ) printf ( "%d ", stack[i] ); printf ( " " );}void grahamScan ()...{ memset ( used, 0x00, sizeof ( used ) ); int top; stack[0] = 0, stack[1] = 1; top = 1; int i; for ( i = 2; i < N; i ++ )
...{ if ( crossDet ( p[stack[top - 1]], p[stack[top]], p[i] ) >= 0 ) stack[++ top] = i; else ...{ while ( top > 0 && crossDet ( p[stack[top - 1]], p[stack[top]], p[i] ) < 0 ) top --; stack[++ top] = i;
} } for ( i = 0; i <= top; i ++ ) used[p[stack[i]].id] = 1; //ps ( top ); for ( i = N - 1; i >= 0; i -- ) ...{ if ( used[i] ) continue; if ( crossDet ( p[stack[top - 1]], p[stack[top]], p[i] ) >= 0 ) stack[++ top] = i; else ...{ while ( top > 0 && crossDet ( p[stack[top - 1]], p[stack[top]], p[i] ) < 0 ) top --; stack[++ top] = i; } } //ps ( top ); int j; double max = 0; for ( i = 0; i <= top; i ++ ) for ( j = 0; j <= top; j ++ ) ...{ double t = hypot ( p[stack[i]].x - p[stack[j]].x, p[stack[i]].y - p[stack[j]].y ); max = max > t ? max : t; } printf ( "%.2f ", max );}void proc ()...{ if ( N == 1 ) printf ( "0.00 " ); if ( N == 2 ) printf ( "%.2f ", hypot ( p[0].x - p[1].x, p[0].y - p[1].y ) ); if ( N >= 3 ) grahamScan ();}int main ()...{ //freopen ( "in.txt", "r", stdin ); while ( init () ) ...{ proc (); } return 0;}