package teralg;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Locale;
import java.util.Scanner;

/**
 * Térinformatikai algoritmusok
 * 3. beadandó: Rendezések
 * @author Máté Cserép <mcserep@outlook.com>
 */
public class SortPerimeter {
    
    public static void main(String[] args) {
        
        // Megyéket tároló dinamikus méretezésű tömb
        ArrayList<County> counties = new ArrayList<County>();
        try
        {
            FileReader fr = new FileReader("hun_megye.txt");
            BufferedReader br = new BufferedReader(fr);

            String line;
            while((line = br.readLine()) != null)
            {
                Scanner sc = new Scanner(line);
                sc.useLocale(Locale.US);

                String name = sc.next();
                Double perimeter = 0.0;
                
                Double firstX = sc.nextDouble();
                Double firstY = sc.nextDouble();
                Double secondX;
                Double secondY;
                while(sc.hasNext())
                {
                    secondX = sc.nextDouble();
                    secondY = sc.nextDouble();
                    Double length = Math.sqrt(Math.pow(secondX - firstX, 2) + Math.pow(secondY - firstY, 2));
                    perimeter += length;
                    
                    firstX = secondX;
                    firstY = secondY;
                }
                
                County county = new County(name, perimeter);
                counties.add(county);
                sc.close();
            }
            br.close();
        }
        catch(IOException ex)
        {
            System.out.println("File handling error: " + ex.getMessage());
        }
        
        // Gyorsrendezés
        quickSort(counties);
        
        // Tömb kiíratása
        System.out.println("Megyék kerület szerint csökkenő sorrendben: ");
        for(int i = 0; i < counties.size(); ++i)
        {
            County county = counties.get(i);
            System.out.println((i + 1) + ". " + county.name);
        }
    }
    
    // Gyorsrendezés
    // Nem generikus szintaxissal: 
    //   private static void quickSort(ArrayList<County> array)
    private static <T extends Comparable<T>> void quickSort(ArrayList<T> array) {
        int n = array.size();
        quickSort(array, 0, n - 1);
    }
    
    // Gyorsrendezés (résztömb)
    // Nem generikus szintaxissal: 
    //   private static void quickSort(ArrayList<County> array, int u, int v)
    private static <T extends Comparable<T>> void quickSort(ArrayList<T> array, int u, int v) {
        if(u >= v) return;
        
        int k = partition(array, u, v);
        quickSort(array, u, k - 1);
        quickSort(array, k + 1, v);
    }
    
    // Segédalgoritmus: pivot elem helyrevitele (partícionálás)
    // Nem generikus szintaxissal: 
    //   private static int partition(ArrayList<County> array, int u, int v)
    private static <T extends Comparable<T>> int partition(ArrayList<T> array, int u, int v) {
        int i = u + 1;
        int j = v;
        while(i <= j) {
            while(i <= v && array.get(i).compareTo(array.get(u)) <= 0)
                ++i;
            while(j >= u + 1 && array.get(j).compareTo(array.get(u)) >= 0)
                --j;
            
            if(i < j) {
                swap(array, i , j);
                ++i;
                --j;
            }
        }
        swap(array, u, i - 1);
        return i - 1;
    }
    
    // Segédalgoritmus: elemcsere
    // Nem generikus szintaxissal: 
    //   private static void swap(ArrayList<County> array, int i, int j)
    private static <T> void swap(ArrayList<T> array, int i, int j) {
        T temp = array.get(i);
        array.set(i, array.get(j));
        array.set(j, temp);
    }
}

// Megye nevét és kerületét tároló, rendezhető struktúra
class County implements Comparable<County> {
    public String name;
    public Double perimeter;
    
    public County(String n, Double p) {
        name = n;
        perimeter = p;
    }

    // Rendezés csökkenő sorrendben kerület szerint
    @Override
    public int compareTo(County o) {
        return o.perimeter.compareTo(perimeter);
    }
}