Expert.
Put your skills to the test.

Problem summary

Points in the plane can be joined directly when they share an x or y coordinate, with Manhattan distance as the edge length. Among all pairs connected by a path, find the largest shortest-path distance; output zero if no distinct connected pair exists.

Constraints

1 ≤ n < 2000; coordinates are positive integers less than 1000.

Worked example

Official example, transcribed with whitespace restored from the PDF.

8
1 6
5 5
5 1
2 2
3 2
2 3
3 3
4 3

4

Solution analysis

1. The direct graph can have quadratically many edges when many points share a line. Within each vertical line, sort by y and connect only consecutive points; do the symmetric construction within each horizontal line, sorting by x. This leaves O(n) edges.
2. Any omitted edge between two points on a line is replaced by the chain of consecutive points between them. The chain length telescopes to their coordinate difference, exactly the omitted edge weight. The sparse graph therefore has all the same shortest-path distances.
3. Run Dijkstra from every point and maximize all finite distances encountered. Disconnected pairs do not participate. In the sample, the vertical pair (5,5),(5,1) has distance four, which is the largest finite distance.

Why it works

Every sparse edge is a permitted original move, so sparse distances cannot be smaller than original distances. Conversely, replacing each original edge by its consecutive-point chain preserves its weight, so sparse distances cannot be larger. Thus the graphs have equal finite distances and connectivity. Dijkstra is correct for nonnegative weights, and all-source enumeration includes every connected pair, yielding the required maximum.

Watch out. Ignore infinite distances from disconnected pairs. A few Dijkstra sweeps do not generally compute the diameter of a graph with cycles.

An independently written complete program with standard headers.

// Key idea: Every sparse edge is a permitted original move, so sparse distances cannot be smaller than
// original distances. Conversely, replacing each original edge by its consecutive-point chain
// preserves its weight, so sparse distances cannot be larger.
#include<algorithm>
#include<functional>
#include<iostream>
#include<limits>
#include<numeric>
#include<queue>
#include<utility>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>x(n),y(n),order(n);
    for(int i=0;i<n;++i){
        cin>>x[i]>>y[i];
    }
    iota(order.begin(),order.end(),0);
    vector<vector<pair<int,int>>>graph(n);
    auto connect=[&](int a,int b,int weight){
        graph[a].push_back({b,weight});
        graph[b].push_back({a,weight});
    };
    sort(order.begin(),order.end(),[&](int a,int b){
        return pair<int,int>{x[a],y[a]}<pair<int,int>{x[b],y[b]};
    });
    for(int i=1;i<n;++i){
        int a=order[i-1],b=order[i];
        if(x[a]==x[b]){
            connect(a,b,y[b]-y[a]);
        }
    }
    sort(order.begin(),order.end(),[&](int a,int b){
        return pair<int,int>{y[a],x[a]}<pair<int,int>{y[b],x[b]};
    });
    for(int i=1;i<n;++i){
        int a=order[i-1],b=order[i];
        if(y[a]==y[b]){
            connect(a,b,x[b]-x[a]);
        }
    }
    const long long INF=numeric_limits<long long>::max()/4;
    long long answer=0;
    for(int source=0;source<n;++source){
        vector<long long>distance(n,INF);
        priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>
            heap;
        distance[source]=0;
        heap.push({0,source});
        while(!heap.empty()){
            auto[d,v]=heap.top();
            heap.pop();
            if(d!=distance[v]){
                continue;
            }
            answer=max(answer,d);
            for(auto[u,weight]:graph[v]){
                if(d+weight<distance[u]){
                    distance[u]=d+weight;
                    heap.push({distance[u],u});
                }
            }
        }
    }
    cout<<answer<<'\n';
}