1. 

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 10397 - Connect the Campus
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1338
*
* @author Dennis Wilfert
* @version 1.0, 10/22/2009
*
* Method : MST
* Status : Accepted
* Runtime: 0.920
*/
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.Scanner;

class Main {

public static void main(String[] args) throws IOException {

Scanner reader = new Scanner(new BufferedInputStream(System.in));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

DecimalFormat df = new DecimalFormat();
df.applyPattern("0.00");

int buildings, existing;
int[][] buildinglist;
int[][] coordinates;
int a, b, head, i, j;
double length;
boolean[][] exists;
boolean[] nodes;

while (reader.hasNextInt()) {


buildings = reader.nextInt();
nodes = new boolean[buildings];
buildinglist = new int[buildings][2];
exists = new boolean[buildings][buildings];

// Gebäudekoordinaten einlesen
for (i = 0; i < buildings; i++) {
buildinglist[i][0] = reader.nextInt();
buildinglist[i][1] = reader.nextInt();
}

// Schauen welche Verbindungen bereits existieren, und diese in ein boolean-Array eintragen
existing = reader.nextInt();
for (i = 0; i < existing; i++) {
a = reader.nextInt() - 1;
b = reader.nextInt() - 1;
exists[a][b] = exists[b][a] = true;
}

// Verbindungslängen zwischen allen Gebäuden berechnen, wenn sie noch nicht existieren
coordinates = new int[buildings > 2 ? (buildings * buildings - 1) / 2 : 2][5];
int k = 0;
for (i = 0; i < buildings; i++) {
for (j = i + 1; j < buildings; j++) {
coordinates[k][0] = i;
coordinates[k][1] = j;
if (!exists[i][j]) {
coordinates[k][2] = (int) (((buildinglist[j][1] - buildinglist[i][1]) * (buildinglist[j][1] - buildinglist[i][1])) + ((buildinglist[j][0] - buildinglist[i][0]) * (buildinglist[j][0] - buildinglist[i][0])));
}
k++;
}
}


// 2-Dimensionales Array nach dem Abstand der Punkte Sortieren
if (k > 1) {
sort(coordinates, 0, k - 1);
}

// Jeweils die vorherigen und die nächste Position zu jedem Wert eintragen
for (i = 0; i < k; i++) {
coordinates[i][3] = i - 1;
coordinates[i][4] = i + 1;
}

///////////////// Prim Algorithmus zum berechnen der Kürzesten Verbindung ////////////////
head = 0;
nodes[0] = true;
length = 0;
// Alle Knoten durchlaufen
for (j = buildings - 1; j > 0; j--) {
i = head;
while (i < k) {
// Steht weder der Anfangs- noch der Endknoten der Straße auf true wird mit dem nächsten Wert weitergemacht
if (!nodes[coordinates[i][0]] && !nodes[coordinates[i][1]]) {
i = coordinates[i][4];
} // Steht mindestens einer der Beiden Knoten der aktuellen Straße auf true
else {
// Ist der Vorgängerwert -1, bekommt die nachfolgende Straße auch -1 als Vorgängerwert
if (coordinates[i][3] == -1) {
coordinates[coordinates[i][4]][3] = coordinates[i][3];
} // Ansonsten bekommt die vorherige Straße den nachfolgerwert als nächste Straße
// und doie nachfolgende Straße die Vorgängerstraße als vorherige Straße
else {
coordinates[coordinates[i][3]][4] = coordinates[i][4];
coordinates[coordinates[i][4]][3] = coordinates[i][3];
}
// Ist nur einer der beiden Knotenpunke der Straße auf true wird der andere Knotenpunkt auch auf true gesetzt und die Länge
// der Straße von der Gesamtlänge des Straßennetzes abgezogen, d.h. die Straße kann ohne Beleuchtung auskommen.
if ((nodes[coordinates[i][0]] && !nodes[coordinates[i][1]]) || (nodes[coordinates[i][1]] && !nodes[coordinates[i][0]])) {
nodes[nodes[coordinates[i][0]] ? coordinates[i][1] : coordinates[i][0]] = true;
length += Math.sqrt(coordinates[i][2]);
// Ist der Vorgängerwert -1 wird der Nachfolgerwert als Startpunkt für die while-Schleife gesetzt, ansonsten wird mit
// dem alten Startwert begonnen
if (coordinates[i][3] == -1) {
head = coordinates[i][4];
}
// Schleife unterbrechen
break;
}
i = coordinates[i][4];
}
}
}
/////////////////////////////////////////////////////////////////////

writer.println(df.format(length));



}
writer.flush();

}

/*
* Sortieren des 2-DImensionalen Arrays mit Quicksort
*/
public static void sort(int[][] a, int start, int end) {
int[] tmp;
int i = start;
int j = end;
int x = a[(start + end) / 2][2];

do {
// Vom Startpunkt aus einen Wert suchen der >= x ist
while (a[i][2] < x) {
i++;
}
// Vom Endpunkt aus einen Wert suchen der <= x ist
while (a[j][2] > x) {
j--;
}

// a[i] und a[j] tauschen
if (i <= j) {
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
} while (i <= j);

if (start < j) {
sort(a, start, j);
}

if (i < end) {
sort(a, i, end);
}
}
}