[2020年10月28日普级组]1408.MSWORLD

$$1408.MSWORLD$$

题目描述

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，描述了农场的坐标。

输出

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

样例输入

40 00 11 11 0

样例输出

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

题目解析

这道题在校网的数据很$氵水沝淼?$，所以暴力就可以过了。但如果想在落谷过，那就要使用亿些恶心的卡常优化（详见代码）

注：这是在落谷上开了O2，再加上一些“奇技淫巧”的卡常才可以过。如果当时评测的人过多，极大可能过不来（有一点是刚好没超时的）

code

#include<cstdio>
#include<iostream>
typedef long long ll;
using namespace std;ll n, x[50005], y[50005], ans;int main ()
{
    scanf ("%lld", &n);if(n == 1){
    printf ("-1"); return 0;}n = min (48000ll, n);for (register int i = 1;i <= n; ++ i){
    scanf ("%lld%lld", &x[i], &y[i]);for(register int j = 1;j < i; ++j)ans = max(ans, (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));}printf ("%lld",ans);return 0;
}