/*************************************************************************
 *  Kompilacja:  javac Point.java
 *  Wykonanie:    java Point
 *
 *  Implementacja punktu o współrzędnych całkowitoliczbowych w przestrzeni dwuwymiarowej.
 *
 *  Jest to ilustracja korzystania z niestatycznego obiektu zgodnego z interfejsem Comparator,
 *  który porządkuje punkty rosnąco według odległości od punktu bazowego.
 * 
 *  % java Point 10
 *  165.8463143998081 (584, 643)
 *  202.85216291674092 (665, 382)
 *  207.88458336298052 (320, 604)
 *  225.39077177204928 (724, 475)
 *  348.8624370722649 (536, 847)
 *  430.5090010673412 (917, 607)
 *  431.26442004876776 (533, 930)
 *  452.3593704125073 (898, 285)
 *  506.5984603213871 (19, 341)
 *  570.7092079159053 (897, 910)
 *
 *************************************************************************/

import java.util.Comparator;
import java.util.Arrays;

public class Point implements Comparable<Point> { 
    private final int x;
    private final int y;

    public final Comparator<Point> BY_DISTANCE_TO = new ByDistanceToComparator();
    public final Comparator<Point> BY_CCW         = new ByCCWComparator();

    public static final Comparator<Point> BY_X = new ByXComparator();
    public static final Comparator<Point> BY_Y = new ByYComparator();

    // Tworzenie i inicjowanie punktu na podstawie pary (x, y)
    public Point(int x, int y) {
       this.x = x;
       this.y = y;
    }

    // Zwraca odległość euklidesową między danym punktem a punktem that
    public double distanceTo(Point that) {
       double dx = this.x - that.x;
       double dy = this.y - that.y;
       return Math.sqrt(dx*dx + dy*dy);
    }

    // Czy a->b->c biegnie przeciwnie do ruchu wskazówek zegara?
    // -1 jeśli zgodne z ruchem wskazówek zegara, +1 jeśli przeciwne, 0 jeśli współliniowe
    public static int ccw(Point a, Point b, Point c) {
       int area2 = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
       if      (area2 < 0) return -1;
       else if (area2 > 0) return +1;
       else                return  0;
    }

    // Dwukrotność dodatniego pola a-b-c
    public static int area2(Point a, Point b, Point c) {
       return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
    }


    // Przekształcanie na łańcuch znaków
    public String toString() {
       return "(" + x + ", " + y + ")";
    }

    // Wyświetlanie punktu za pomocą StdDraw
    public void draw() {
       StdDraw.point(x, y);
    }

    // Wyświetlanie linii od danego punktu do punktu that
    public void drawTo(Point that) {
       StdDraw.line(this.x, this.y, that.x, that.y);
    }

    // Porządek naturalny: porównuje według współrzędnej y; równe 
	// punkty porównuje według współrzędnej x
    public int compareTo(Point that) {
       if (this.y < that.y) return -1;
       if (this.y > that.y) return +1;
       if (this.x > that.x) return -1;
       if (this.x < that.x) return +1;
       return 0;
    }

    // Czy współrządne x i y dwóch punktów są takie same?
    public boolean equals(Object y) {
       if (y == this) return true;
       if (y == null) return false;
       if (y.getClass() != this.getClass()) return false;
       Point that = (Point) y;
       return (this.x == that.x) && (this.y == that.y);
    }

    /**********************************************************************
     *  Obiekt Comparator porównujący punkty według kąta biegunowego
     *  względem danego punktu. Kąt biegunowy jest mierzony względem
     *  promienia biegnącego z danego punktu w prawo. Punkty o równych 
     *  kątach są porównywane względem odległości od danego punktu.
     *
     *  Reguła porównywania według odległości jest wykorzystywana tylko dla 
     *  "zdegenerowanych" przypadków (jeśli występują trzy współliniowe 
     *  punkty na otoczce wypukłej, można wykryć tylko pierwszy i ostatni punkt).
     *
     *  Warunek wstępny:  q1 i q2 znajdują się wyżej względem p.
     *
     *  Technicznie narusza to kontrakt dla metody compare(), jeśli
     *  zostanie na wywołana dla punktów o współrzędnej y mniejszej niż p.
     *
     **********************************************************************/
    private class ByCCWComparator implements Comparator<Point> {
       public int compare(Point q1, Point q2) {
          int ccw = ccw(Point.this, q1, q2);
          if (ccw == -1) return -1;
          if (ccw == +1) return +1;

          int dx1 = q1.x - x;
          int dx2 = q2.x - x;
          int dy1 = q1.y - y;
          int dy2 = q2.y - y;

          // Zakładamy, że dy1 >= 0 && dy2 >= 0;  
		  // inaczej naruszony jest kontrakt dla metody compare().
          // Równe kąty wymagają porównania punktów według odległości od danego punktu.
          // Możliwe powinno być zastąpienie obliczania odległości 
          // projekcją, ponieważ punkty są współliniowe
          if      (dx1*dx1 + dy1*dy1 < dx2*dx2 + dy2*dy2) return -1;
          else if (dx1*dx1 + dy1*dy1 > dx2*dx2 + dy2*dy2) return +1;
          else                                            return  0;
       }
    }

    
    
    // Porównuje punkty według odległości do danego punktu
    private class ByDistanceToComparator implements Comparator<Point> {
        public int compare(Point p, Point q) {
            if      (distanceTo(p) < distanceTo(q)) return -1;
            else if (distanceTo(p) > distanceTo(q)) return +1;
            else                                    return  0;
        }
    }

    // Porównuje punkty według współrzędnej x, a równe - według współrzędnej y
    private static class ByXComparator implements Comparator<Point> {
        public int compare(Point p, Point q) {
           if (p.x < q.x) return -1;
           if (p.x > q.x) return +1;
           if (p.y < q.y) return -1;
           if (p.y > q.y) return +1;
           return 0;
        }
    }

    // Porównuje punkty według współrzędnej y, a równe - według współrzędnej x
    private static class ByYComparator implements Comparator<Point> {
        public int compare(Point p, Point q) {
           if (p.y < q.y) return -1;
           if (p.y > q.y) return +1;
           if (p.x < q.x) return -1;
           if (p.x > q.x) return +1;
           return 0;
        }
    }



   // Generuje N losowych punktów i sortuje je według odległości do (500, 500)
   public static void main(String[] args) {
      int N = Integer.parseInt(args[0]);
      Point[] points = new Point[N];
      for (int i = 0; i < N; i++) {
          int x = StdRandom.uniform(1000);
          int y = StdRandom.uniform(1000);
          points[i] = new Point(x, y);
      }
      Point base = new Point(500, 500);
      Arrays.sort(points, base.BY_DISTANCE_TO);
      for (int i = 0; i < N; i++) {
          StdOut.println(base.distanceTo(points[i]) + " " + points[i]);
      }
   }
}
