# Poj Solution 3102

```http://poj.org/problem?id=3102

/* @author: */
import java.util.*;
import java.io.*;
import java.lang.reflect.Array;

public class Main {
static double dis[][];
static int e[][];
static int [] x, y, en;

static double distance( int a, int b ) {
return Math.sqrt( (x[a]-x[b])*(x[a]-x[b]) +
(y[a]-y[b])*(y[a]-y[b]) );
}

static void dfs( int k, int f, double [] dis, double s ){
dis[k] = s;
int j;
for( int i=0; i< en[k]; i++ ) {
if( e[k][i] != f ) {
j = e[k][i];
dfs( j, k, dis, s+distance( k, j ) );
}
}
}

static public void main( String [] str ) throws Exception{
Scanner cin = new Scanner( System.in );
int n = cin.nextInt();
x = new int[n+1];
y = new int[n+1];
en = new int[n+1];
dis = new double[n+1][n+1];
e = new int[n+1][n+1];

for( int i=1; i<=n; i++ ) {
x[i] = cin.nextInt();
y[i] = cin.nextInt();
}

int a, b;
double t, ans = 0;
for( int i=1; i<=n; i++ ) {
a = cin.nextInt();
b = cin.nextInt();
e[a][en[a]++] = b;
e[b][en[b]++] = a;
}

for( int i=0; i<=n; i++ )
dfs( i, -1, dis[i], 0 );

a = -1;
b = -1;
for( int i=0; i<=n; i++ )
for( int j=i+1; j<=n; j++ ) {
int k;
for( k =0; k<=n; k++ )
if( k!= i && k!=j &&
(x[i]-x[k])*(y[j]-y[k])-(y[i]-y[k])*(x[j]-x[k]) == 0 &&
(x[i]-x[k])*(x[j]-x[k])+(y[i]-y[k])*(y[j]-y[k]) <= 0 )
break;
if( k <= n )
continue;
t = - dis[i][j] + distance( i, j );
if( t < ans ) {
ans = t;
a = i;
b = j;
}
}
System.out.println();

if( a < 0 )
System.out.println( -1 );
else
System.out.println( a+" "+b );
}
}
```
This entry was posted in poj. Bookmark the permalink.