Solution Notes (Alex Chen): The following shows one possible way to solve this problem.

We can create a graph representation of the farms by creating 5 nodes for each farm: one for the farm itself and one for each of the adjacent (x, y) coordinates. Let a right-angle path be a path that changes direction at most once and consists only of movement up, down, left, or right. We add an edge between every pair of nodes (x1, y1) and (x2, y2) if it is possible to go from (x1, y1) to (x2, y2) using a right-angle path that does not intersect any farms, except at its endpoints. The length of this edge is the "Manhattan" distance (|x1-x2|+|y1-y2|).

To check whether an edge is valid, we check the path (x1, y1) -> (x1, y2) -> (x2, y2) and the path (x1, y1) -> (x2, y1) -> (x2, y2). We can loop through all N farms and see if either right-angle path intersects any farms. There exist more efficient ways to check, but since N <= 100, this algorithm is fast enough.

Using this new graph, which contains at most 5N nodes and (5N)^2 edges, we can use a shortest path algorithm to find the shortest path lengths between each farm. This solution works because each shortest path between farms is achievable using only the 5N nodes and right-angle paths. With Dijkstra's algorithm, we can find each shortest path in O(N^2). By finding shortest paths for each of the N farms, the entire problem can be solved in O(N^3).

``````
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <queue>

using namespace std;

struct pt
{
int x, y;
pt(int a, int b)
{ x = a, y = b; }
} ;

int N, x, y, indx;
set<pair<int, int> > points; // keeps track of which (x, y) coordinates are farms
vector<pt> nodes;

// Returns the taxicab distance between nodes[a] and nodes[b].
int length(int a, int b)
{
return abs(nodes[a].x - nodes[b].x) + abs(nodes[a].y - nodes[b].y);
}

// Returns whether the first point (x1, y1) is on the segment (x2, y2) -> (x3, y3).
bool in_segment(int x1, int y1, int x2, int y2, int x3, int y3)
{
if(x2 == x3)
return x1 == x2 && y1 > min(y2, y3) && y1 < max(y2, y3);
else if(y2 == y3)
return y1 == y2 && x1 > min(x2, x3) && x1 < max(x2, x3);
else // invalid
return true;
}

// Returns whether a right-angle path from nodes[a] to nodes[b] is possible (does not intersect any of the N original points, except potentially at endpoints).
bool possible(int a, int b)
{
// Method 1: travel vertical first, then horizontal
bool good1 = nodes[a].x == nodes[b].x || nodes[a].y == nodes[b].y || points.find(make_pair(nodes[a].x, nodes[b].y)) == points.end();
for(int i = 0; i < N; i++)
if(in_segment(x[i], y[i], nodes[a].x, nodes[a].y, nodes[a].x, nodes[b].y) || in_segment(x[i], y[i], nodes[a].x, nodes[b].y, nodes[b].x, nodes[b].y))
{
good1 = false;
break;
}
if(good1)
return true;

//Method 2: travel horizontal first, then vertical
bool good2 = nodes[a].x == nodes[b].x || nodes[a].y == nodes[b].y || points.find(make_pair(nodes[b].x, nodes[a].y)) == points.end();
for(int i = 0; i < N; i++)
if(in_segment(x[i], y[i], nodes[a].x, nodes[a].y, nodes[b].x, nodes[a].y) || in_segment(x[i], y[i], nodes[b].x, nodes[a].y, nodes[b].x, nodes[b].y))
{
good2 = false;
break;
}
if(good2)
return true;

return false;
}

// Returns the length of the shortest path from nodes[a] to nodes[b].
bool vis;
int dist, infinity = 1023456789;
int dijkstra(int a, int b)
{
for(int i = 0; i < nodes.size(); i++)
{
dist[i] = infinity;
vis[i] = false;
}
// Don't visit farms (except for the start and end locations).
for(int i = 0; i < N; i++)
if(indx[i] != a && indx[i] != b)
vis[indx[i]] = true;

dist[a] = 0;
for(int i = 0; i < nodes.size(); i++)
{
int next = 0;
for(int j = 0; j < nodes.size(); j++)
if(!vis[j] && (dist[j] < dist[next] || vis[next]))
next = j;
if(vis[next] || dist[next] == infinity)
return -1;
if(next == b)
return dist[next];
vis[next] = true;
for(int j = 0; j < adj[next].size(); j++)
}
return -1;
}

int main()
{
FILE * w = fopen("delivery.in", "r");
FILE * o = fopen("delivery.out", "w");

fscanf(w, "%d", &N);
for(int i = 0; i < N; i++)
{
fscanf(w, "%d %d", &x[i], &y[i]);
points.insert(make_pair(x[i], y[i]));
}

// Make nodes
for(int i = 0; i < N; i++)
for(int a = -1; a <= 1; a++)
for(int b = -1; b <= 1; b++)
{
if(a == 0 && b == 0)
{
nodes.push_back(pt(x[i], y[i]));
indx[i] = nodes.size() - 1;
}
else if(a * b == 0 && points.find(make_pair(x[i] + a, y[i] + b)) == points.end())
nodes.push_back(pt(x[i] + a, y[i] + b));
}

// Make edges
for(int i = 0; i < nodes.size(); i++)
for(int j = i + 1; j < nodes.size(); j++)
if(possible(i, j))
{
}

// Dijkstra's Algorithm
int answer = 0;
for(int i = 0; i < N; i++)
{
int next = dijkstra(indx[i], indx[(i + 1) % N]);
if(next < 0)
{