There are not that many city's in any given country so N^2 is probably not a big deal. However, you can get approximate results by drawing a line at every angle through a country and then moving that line up and down. Then just look for city's near any good candidate lines.
> drawing a line at every angle through a country and then moving that line up and down.
This part is quite messy. For every given (c1,c2) city pair, you'd get 1 straight line that connects c1 to c2. Then for every city ck, you need info on whether ck is above that line or below - you can compute that by point-slope geometry with the lat-long coordinates ( given point p(x,y) & line l with some slope, is p above l or below ).
