Областная олимпиада по информатике. 10-11 классы. 2014-2015 учебный год.


Задача B. Тима и точки

Ограничение по времени:
1 секунда
Ограничение по памяти:
64 мегабайта

Один очень сильный мальчик по имени Тима поймал Вас на переулке Манхэттена. Единственный шанс уйти без повреждений — решить следующую задачу! Даны $N$ точек в пространстве. Требуется найти две самые удалённые точки. Расстояние между точками $(x_1; y_1; z_1)$ и $(x_2; y_2; z_2)$ равно $|x_1-x_2|+|y_1-y_2| + |z_1-z_2|$. Решите задачу и спасите себя!
Формат входного файла
В первой строке задано целое число $N$ $(2 \le N \le 10^5)$ — количество точек. В следующих $N$ строках заданы сами точки — по три целых числа $x_i;$ $y_i;$ $z_i$ на каждой строке. Все координаты точек находятся в интервале $[-10^6 \ldots 10^6]$.
Формат выходного файла
Выведите ответ к задаче.
Примеры:
Вход
4
 0  9 -8
-2  5  3
 6 -6  2
 7  1  6
Ответ
31
Замечание
Ответ 31, потому что расстояние между 1-ой и 3-ей точками равно $|0-6| + |9-(-6)| + |-8-2| = 6 + 15 + 10 = 31;$
$2 \le N \le 10^4$ — для $30\%$ тестов.
посмотреть в олимпиаде

Комментарий/решение:

пред. Правка 2   -2
2018-11-24 15:45:45.0 #

показать/скрыть код

пред. Правка 2   -2
2018-12-14 12:13:04.0 #

TL

  -1
2018-12-20 09:47:57.0 #

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N=10e5+7;

int a[N],b[N],c[N];

main(){

int mx=-N;

int n;

cin>>n;

for(int i=1;i<=n;++i){

cin>>a[i]>>b[i]>>c[i];

}

for(int i=1;i<=n;++i){

for(int j=1;j<=n;++j){

mx=max(mx,abs(a[i]-a[j])+abs(b[i]-b[j])+abs(c[i]-c[j]));

}

}

cout<<mx;

}ВВедите тескт...показать/скрыть код