package teralg;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Locale;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;

/**
 * Térinformatikai algoritmusok
 * 2. beadandó: Alapvető adatszerkezetek
 * @author Máté Cserép <mcserep@outlook.com>
 */
public class MultipleMaxPerimeter {
    
    public static void main(String[] args) {
        
        // Megyéket tároló elsőbbségi sor
        PriorityQueue<County> counties = new PriorityQueue<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());
        }
        
        // N értékének beolvasása
        System.out.print("n := ");
        Scanner in = new Scanner(System.in);
        Integer n = Math.min(in.nextInt(), counties.size());
        
        // Az első N megye áthelyezése egy verembe az elsőbbségi sorból
        Stack<County> maxStack = new Stack<County>();        
        for(int i = 0; i < n; ++i)
        {
            County county = counties.poll();
            maxStack.push(county);
        }
        
        // Verem kiíratása
        System.out.println("Legnagyobb kerületű megyék: ");
        for(int i = 0; i < n; ++i)
        {
            County county = maxStack.pop();
            System.out.println((n - i) + ". " + county.name);
        }
    }
}

// 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);
    }
}