模拟赛3

1.MSWORLD

时间限制:10000MS
内存限制:256000KB

题目描述
Bessie , Farmer John 的优选牛，刚刚获得了一个牛科动物选美比赛的冠军！并得到了“世界奶牛小姐”的头衔。因此，Bessie将进行一场环球农场旅行，共N个农场(2<=N<=50,000)，依次传播农场主和奶牛们之间的亲善友好。为了简单起见，世界可以看作一个二维平面，每座农场的位置用二维坐标(x,y)表示，x,y是-10,0000到10,0000的整数。没有两座农场处于同一个位置上。

哪怕Bessie在两个农场间都是走的直线，在某些农场间的距离还是很远,所以她想随身携带一只装满了干草的箱子,这样她在每一段行程都有充足的食物。因为Bessie在她每到达一个农场后都要重新装满她的箱子,她想弄清楚她可能要走的最大距离,以此来决定它必须携带多大的箱子。帮帮Bessie吧!你只要求出任意两点距离的最大值就可以了。

输入
第一行，一个整数，N。第2～N+1行，两个整数X，Y，描述了农场的坐标。

输出
一个整数，最大距离的平方。

输入样例
4

0 0

0 1

1 1

1 0

输出样例
2

样例说明
农场1（0,0）和农场3（1,1）的距离为 2的开方。

说明
数据范围限制
2<=N<=50,000

解题思路

暴力
没想到吧，暴力也能过

洛谷有原题旋转卡壳
在输出后加一个玄学优化就AC了

scanf("%lld",&n);
n=min(40000ll,n);//优化

注意：当n=1时，输出-1

AC代码

#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
long long n,ans,x[50005],y[50005];
int main()
{
   
	scanf("%lld",&n);
    n=min(40000ll,n);//玄学优化
	if(n==1){
   printf("-1");return 0;}//特判1
	for(long long i=1;i<=n;i++)
	 scanf("%lld%lld",&x[i],&y[i]);
	for(long long i=1;i<n;i++)//一个一个暴力
	 for(long long j=i+1;j<=n;j++)
	 {
   
	 	long long xx=abs(x[i]-x[j])*abs(x[i]-x[j])+abs(y[i]-y[j])*abs(y[i]-y[j]);//勾股定理求距离
	 	ans=max(ans,xx);
	 }
	printf("%lld",ans); 
	return 0;
}

谢谢