1. 


/* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #638 (Finding Rectangles)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=579
*
* @author Dennis Wilfert
* @author Johann Studt
* @version 1.0, 05/23/2009
*
* Status : Accepted
* Runtime: 0.664
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;


public class Main {
/* StringBuilder für die Ausgabe */
static StringBuilder output = new StringBuilder();
/* Liste der Koordinatenbuchstaben */
static char[] coordinateNames;
/* Liste der Koordinaten */
static int[][] coordinates;

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

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
// Anzahl der Koordinaten auslesen
int number = Integer.parseInt(reader.readLine().trim());
// Nummer des aktuellen sets
int count=0;
// StringTokenizer zum auslesen
StringTokenizer token;

while(number != 0){

// Array für Koordinatenbuchstaben anlegen
coordinateNames = new char[number];
// Array für Koordinaten anlegen
coordinates = new int[number][2];

// Koordinaten auslesen
for(int i = 0; i< number; i++){
token = new StringTokenizer(reader.readLine());
coordinateNames[i] = token.nextToken().charAt(0);
coordinates[i][0] = Integer.parseInt(token.nextToken());
coordinates[i][1] = Integer.parseInt(token.nextToken());
}

// Aktuelle Set-nummer an die Ausgabe anhängen
count++;
output.append("Point set " + count +":");

// Quadrate suchen
rectangle(number);

// Anzahl der Koordinaten auslesen
number = Integer.parseInt(reader.readLine().trim());
}
// Ausgeben
System.out.print(output);

}

//static char[] rectangleChars;

//static int[][] rectangleCoordinates;
/* Gefundene Koordinatennamen */
static LinkedList<Character> found;

/*
* Erste Koordinate für das Rechteck suchen und das Unterprogramm zum
* suchen der Rechtecke aufrufen. Anschließend alle Rechtecke in die Ausgabe schreiben
*/
static void rectangle(int number){

found = new LinkedList<Character>();
// Startkoordinate nehmen und das Unterprogramm zum suchen der Rechtecke aufrufen
for(int i = 0; i < number; i++){
// Koordinatennamen des aktuell gesuchten rechtecks
char[] rectangleChars = new char[4];
// Koordinaten des aktuell gesuchten rechtecks
int[][] rectangleCoordinates = new int[4][2];
rectangleChars[0]= coordinateNames[i];
rectangleCoordinates[0]= coordinates[i];
rectangleChars = findnext(rectangleChars, rectangleCoordinates, 1, number);
}

// Für alle gefundenen Rechtecke die formatierte Ausgabe erzeugen
int i=0;
if(found.size()>0){
output.append("\n");
for(char charlist: found){

if(i%4==0)output.append(" ");
output.append(charlist);
i++;
if(i%40==0)output.append("\n");
}
if(i%40!=0)output.append("\n");
}
else output.append(" No rectangles\n");

}

/*
* Rechtecke suchen und in found eintragen
*/
static char[] findnext(char[] rectangleChars, int[][] rectangleCoordinates, int n, int number){
// Feststellen ob der Wert bereits in rectangleChars steht
boolean exists;
// Wenn n 4 ist wurde ein komplettes Rechteck gefunden
if(n==4)
return rectangleChars;

for(int k = 0; k < number; k++){
// Zweite Ecke
if(n==1)
// y-Koordinate suchen die gleich der y-Koordinate der ersten Ecke ist
if(coordinates[k][1]==rectangleCoordinates[0][1]){
exists=false;
// Prüfen ob die Koordinate bereits existiert
for(int q = 0; q < n; q++){
if(rectangleChars[q]== coordinateNames[k])exists = true;
}
// Existiert die Koordinate noch nicht, dann eintragen und die nächste Ecke suchen
if(exists==false){
rectangleChars[n]=coordinateNames[k];
rectangleCoordinates[n]=coordinates[k];
findnext(rectangleChars, rectangleCoordinates, n+1, number);
rectangleChars[n]=0;
rectangleCoordinates[n]= new int[2];
}
}
// Dritte ecke
if(n==2)
// x-Koordinate finden die gleich der x-Koordinate der zweiten Ecke ist
if(coordinates[k][0]==rectangleCoordinates[1][0]){
exists=false;
// Prüfen ob die Koordinate bereits existiert
for(int q = 0; q < n; q++){
if(rectangleChars[q]== coordinateNames[k])exists = true;
}
// Existiert die Koordinate noch nicht, dann eintragen und die nächste Ecke suchen
if(exists==false){
rectangleChars[n]=coordinateNames[k];
rectangleCoordinates[n]=coordinates[k];
findnext(rectangleChars, rectangleCoordinates, n+1, number);
rectangleChars[n]=0;
rectangleCoordinates[n]= new int[2];
}
}
// Vierte Ecke
if(n==3)
// y-Koordinate suchen die gleich der y-Koordinate der dritten Ecke ist
// die x-Koordinate muss dabei gleich der x-Koordinate der ersten Ecke sein
if(coordinates[k][1]==rectangleCoordinates[2][1] && coordinates[k][0]==rectangleCoordinates[0][0]){
exists=false;
// Prüfen ob die Koordinate bereits existiert
for(int q = 0; q < n; q++){
if(rectangleChars[q]== coordinateNames[k])exists = true;
}
// Existiert die Koordinate noch nicht, dann eintragen und an found anhängen
if(exists==false){
rectangleChars[n]=coordinateNames[k];
rectangleCoordinates[n]=coordinates[k];
if(rectangleCoordinates[0][0]<rectangleCoordinates[1][0]&&rectangleCoordinates[0][1]>rectangleCoordinates[3][1]){
for(char chr: rectangleChars)
found.add(chr);
rectangleChars[n]=0;
rectangleCoordinates[n]= new int[2];
}
}
}
}

return rectangleChars;

}


}