import com.kg.fss.entity.City;
import com.kg.fss.util.Algorithm;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Arrays;
import static java.lang.Double.POSITIVE_INFINITY;


public class siteSelection {
    public static void main(String[] args) throws Exception {

        /*
         * Read data
         */
        BufferedReader br = new BufferedReader(new FileReader("C:\\javaProject\\fss\\src\\main\\java\\com\\kg\\fss\\util\\input_assgin01_03.dat"));
        String s = null;
        int size = Integer.parseInt(br.readLine());
        /*
         * 1 Define the candidate point coordinates and the weights corresponding to each point
         */
        double[] x = new double[size];
        double[] y = new double[size];
        double[] xweight = new double[size];
        double[] yweight = new double[size];
        String[] city = new String[size];
        int i = 0;
        while((s = br.readLine()) != null){
            String[] a = s.split(",");
             city[i]= a[3];
            x[i] = Double.parseDouble(a[0]);
            y[i] = Double.parseDouble(a[1]);
            xweight[i] = Double.parseDouble(a[2]);
            yweight[i] = Double.parseDouble(a[2]);
            i++;
        }
        siteSelection siteSelection = new siteSelection();
        double[] xtemp = new double[size];
        xtemp= Arrays.copyOf(x,size);
        double[] ytemp = new double[size];
        ytemp=Arrays.copyOf(y,size);
        City resultCity = siteSelection.initarea(x, y, xweight, yweight,xtemp,ytemp,city);
        System.out.println("The result is:");
        System.out.println(resultCity.getCityLat());
        System.out.println(resultCity.getCityLon());
        System.out.println(resultCity.getCityName());
    }




    /**
     * Quick sort (at the same time, the weights corresponding to each point are adjusted in turn)
     *
     * @param attr  
     * @param weight  
     * @param low  
     * @param height  
     */
    public  void pxres(double[] attr, double[] weight, int low, int height){
        double temp = 0;
        double temp1 =0;
        int i = low;
        int j = height;

        if(low < height){
            temp = attr[low];
            temp1 = weight[low];

            while(i != j){
                while(j > i && attr[j] >= temp){
                    --j;
                }
                if(i < j){
                    attr[i] = attr[j];
                    weight[i] = weight[j];
                    ++i;
                }
                while(i < j && attr[i] < temp){
                    ++i;
                }
                if(i < j){
                    attr[j] = attr[i];
                    weight[j] = weight[i];
                    --j;
                }
            }

            attr[i] = temp;
            weight[i] = temp1;
            pxres(attr, weight, low, i - 1);
            pxres(attr, weight, i + 1, height);
        }
    }

    /**
     * Find the coordinates corresponding to the weighted median for each axis
     * @param addr  
     * @param Weights  
     * @param zhou  
     * @return 
     */
    public  double axis(double [] addr, double [] Weights, String zhou){

        /*
         * Quickly sort each axis coordinate and adjust the corresponding weights
         */

        pxres(addr, Weights, 0, addr.length - 1);


        /*
         * 3 Sum of weights of all candidate points
         */

        double sumweight = 0;
        for(int i = 0; i < Weights.length; i++){
            sumweight += Weights[i];
        }

        /*
         * 4 Find the weighted median in the latitude direction
         */

        double sum = 0;
        for(int i = 0; i < Weights.length; i++){
            sum += Weights[i];
            if(sum >= sumweight / 2){
                return addr[i];
            }
        }

        return 0;
    }

    /**
     * Method of finding flight service station coordinates
     * @param Xaxis  
     * @param Yaxis  
     * @param XWeights  
     * @param YWeights  
     */
    public  City initarea(double[] Xaxis, double[] Yaxis, double[] XWeights, double[] YWeights,double[] x,double[] y,String[] citys){

        /*
         * 2 Latitude and longitude are processed separately (Note: the weights corresponding to the order of the corresponding axes are adjusted accordingly to keep them one-to-one)
         * 2.1 Quick sort of latitude coordinate points
         */
        double px = axis(Xaxis, XWeights, "Latitude");
        /*
         * 2.2 Quick sort of longitude coordinate points
         */
        double py = axis(Yaxis, YWeights, "longitude");

        /*
        2.3Determine the location of the nearest town point
         */
        City result = new City();

        result = searchCity(px,py,x,y,citys);


        /*
         * Print the service station location
         */
        return result;
    }

    /**
     *
     * @param x
     * @param y
     * @param xs
     * @param ys
     * @return
     */
    public  City searchCity(double x, double y, double[] xs,double[] ys,String[] citys){
        City  result = new City();
        double minDistance = POSITIVE_INFINITY;
        for (int i=0;i<xs.length;i++) {
            double tempDistance = Algorithm.GetDistance(x,y,xs[i],ys[i]);
            if (tempDistance<minDistance){
                minDistance=tempDistance;
               result.setCityLat(xs[i]);
               result.setCityLon(ys[i]);
               result.setCityName(citys[i]);
            }
        }
        return result;
    }
}

