EOJ 1019 着彈點

着彈點

Time Limit:1000MSMemory Limit:30000KB

Total Submit:482Accepted:62

Description

炮兵某部進行實彈射擊,對一個平面區域裡連續開炮,得到了很多的彈坑.當射擊完成後,作為技術人員的你,

想要得到一個重要的參數,就是相隔距離最大的炮彈着彈點的距離.

Input

多組資料，每組第一行n代表點數，接着n行為着彈點的坐标，坐标為正整數，不超過1000000。

2<=n<=30000。

Output

每組一行，求出相隔距離最大的兩個着彈點之間的距離，保留2位小數

Sample Input

3

1 2

3 4

5 6

Sample Output

5.66

有時AC也靠rp的，雖然這樣很沒節操。。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
struct point{
	double x,y;
};
bool cmp1(point a,point b){
	return a.x < b.x;
}
bool cmp2(point a,point b){
	return a.y < b.y;
}
point p[30005];
double dis(point a,point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		for(int i = 0;i < n ;i ++){
			scanf("%lf%lf",&p[i].x,&p[i].y);
		}
		double ans = 0.0;
		sort(p,p+n,cmp1);
		for(int i = 0;i < n && i < 3000;i ++){
			for(int j = n-1;j >=0 && j >= n-3001; j--){
				ans = max(ans,dis(p[i],p[j]));
			}
		}
		sort(p,p+n,cmp2);
		for(int i = 0;i < n && i < 3000;i ++){
			for(int j = n-1;j >= 0 && j >= n-3001; j--){
				ans = max(ans,dis(p[i],p[j]));
			}
		}
		printf("%.2lf\n",ans);
	}
	return 0;
}