import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.*;

public class Diam extends JFrame implements MouseListener
{
  LinkedList<Point> points = new LinkedList<Point>(); // storage for points
  LinkedList<Point> convHull = new LinkedList<Point>();   // storage for CH
  Point origin = new Point();                      // CH origin
  Point antiPair = new Point(0,0);                 // storage for the diameter

  public static void main(String[] args)
  {
    Diam application = new Diam();
    application.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  }

  public Diam()
  {
    Toolkit toolkit = Toolkit.getDefaultToolkit();
    Dimension screenSize = toolkit.getScreenSize();
    int screenWidth = screenSize.width;
    int screenHeight = screenSize.height;
    setSize(3*screenWidth/4, 3*screenHeight/4);
    setLocation(screenWidth/8, screenHeight/8);
    setTitle("Diamater of a point set");

    Container pane = getContentPane();
    pane.setBackground(new Color(0xffffcc));       // applet background
    addMouseListener(this);
    setVisible(true);
  }

// this method processes the mouse events caused by clicking a button
  public void mousePressed(MouseEvent e) 
  { 
    if (e.getButton() == MouseEvent.BUTTON1)       // left button pressed
    {
      points.add(new Point(e.getX(), e.getY()));   // save the new point
      convHull = grahamScan(points);               // update CH
      antiPair = diam(convHull);                   // compute the diameter
      repaint();                                   // display it
    }
    else if (e.getButton() == MouseEvent.BUTTON3)  // right button pressed
    {
      points.clear();                              // delete all points
      convHull.clear();                            // clear the CH
      repaint();                                   // clear the screen
    }
  }

// this method constructs CH for the entered set of points. It implements the
// Grahan Scan algorithm.
  public LinkedList<Point> grahamScan(LinkedList<Point> pts)
  {
    LinkedList<Point> stack = new LinkedList<Point>();// stack implemented as a
    if (pts.size() < 3) return(stack);             // linked list to get an
                                                   // access to the 2nd el-t

    Point[] ptsArray = new Point[pts.size()];      // convert linked list into
                                                   // an array for sorting
    origin = new Point(Integer.MAX_VALUE, Integer.MAX_VALUE);
    for (int i=0; i<pts.size(); i++)
    {
      Point p = pts.get(i);                        // retrieve a point
      ptsArray[i] = p;                             // insert it into array
      if ((p.y < origin.y) || ((p.y == origin.y) && (p.x < origin.x)))
        origin = p;                                // update the CH origin
    } 
    points.clear();

    Comparator<Point> c = new Comparator<Point>()  // comparator that orders
    {                                              // the points according to
      public int compare(Point p1, Point p2)       // increasing angle for
      {                                            // sorting
        double arg1 = Math.atan2(p1.y - origin.y, p1.x - origin.x);
        double arg2 = Math.atan2(p2.y - origin.y, p2.x - origin.x);
        if (arg1 < arg2) return(-1);               // compare the tangents
        else if (arg1 > arg2) return(1);
        else                                       // tangents are the same
        {                                          // compare the distances
          double dist1 = (p1.x - origin.x)*(p1.x - origin.x) +
                         (p1.y - origin.y)*(p1.y - origin.y);
          double dist2 = (p2.x - origin.x)*(p2.x - origin.x) +
                         (p2.y - origin.y)*(p2.y - origin.y);
          if (dist1 < dist2) return(-1);
          else if (dist1 > dist2) return(1);
          else return(0);
        }
      }
    };
    Arrays.sort(ptsArray, c);                // MergeSort the points
    points = removeDuplicates(ptsArray);     // remove possible duplicates
    if (points.size() < 3) return(stack);

    stack.addFirst(points.get(0));           // the Graham Scan starts here
    stack.addFirst(points.get(1));           // add first 3 points to stack
    stack.addFirst(points.get(2));
    for (int i=3; i<points.size(); i++)      // loop over all remaining pts
    {
      Point p2 = points.get(i);              // retrieve a new point
      int crossProduct;
      do
      {
        Point p1 = stack.getFirst();         // point on the top of stack 
        Point p0 = stack.get(1);             // next-to-top point
        crossProduct = (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);

        if (crossProduct <= 0)               // check the turn direction
          stack.removeFirst();               // remove the top of stack from CH
      } while (crossProduct < 0);

      stack.addFirst(p2);                    // add the new point to CH
    }
    stack.addFirst(origin);                  // close the CH polygon
    return(stack);                           // return CH to the caller
  }

// this method computes the diameter of the entered point set
  public Point diam(LinkedList<Point> pts)
  {
    Point antiPair = new Point(0, 0);
    if (pts.size() == 2) antiPair.y = 1;     // 2-point polygon
    if (pts.size() <= 2) return(antiPair);   // 1- or 2-point polygon

    pts.removeLast();                        // get rid of the duplicate org
    Point[] pts2 = (Point[]) pts.toArray(new Point[pts.size()]);
    System.out.println("\n" + pts2.length + " points in CH");

    int n = pts2.length;
    int p = n-1;                             // line 1 of code (p = p_i)
    int q = 0;                               // line 2 of code (q = q)
    int p1 = 0;                              // p1 = p_{i+1}
    int q1 = 1;                              // q1 = Next(pq)

    LinkedList<Point> antiPairs = new LinkedList<Point>(); // antipodal pairs 
    while (dist(pts2[p], pts2[p1], pts2[q1]) > 
           dist(pts2[p], pts2[p1], pts2[q]))
    {
      q = q1;                                // line 3
      q1 = (q1+1) % n;
    }
    int q0 = q;                              // line 4
    System.out.println("q_0 = " + q0);

    while ( q != 0 )                         // line 5
    {
      p = p1;                                // update p_i
      p1 = (p1+1) % n;                       // update p_{i+1}
      antiPairs.add(new Point(p, q));        // line 7
      System.out.println("Line 7: adding (" + p + ", " + q + ")");
      while (dist(pts2[p], pts2[p1], pts2[q1]) >= 
             dist(pts2[p], pts2[p1], pts2[q]))
      {
        q = q1;
        q1 = (q1+1) % n;                     // q1 = Next(q)

        if ((p != q0) || (q != 0))           // line 10
        {
          antiPairs.add(new Point(p, q));
          System.out.println("Line 10: adding (" + p + ", " + q + ")");
        }
        else
          break;
      }                                         
    }

  // now all antipodal pairs are stored in (p,q) and we compute the maximum
  // distance for those pairs. This maximum distance equals the diameter
    double d_max = 0;
    for (int i=0; i<antiPairs.size(); i++)
    {
      Point pair = antiPairs.get(i);
      double dist = (pts2[pair.x].x - pts2[pair.y].x)*
                    (pts2[pair.x].x - pts2[pair.y].x) +
                    (pts2[pair.x].y - pts2[pair.y].y)*
                    (pts2[pair.x].y - pts2[pair.y].y);
      if (dist > d_max)
      {
        d_max = dist;
        antiPair = pair;
      }
    }
    pts.add(pts.getFirst());
    System.out.println("Diam: (" + antiPair.x + ", " + antiPair.y + ")");
    return(antiPair);
  }

  // this function returns the distance between the point q and the line
  // passing through the points p1 and p2
  public double dist(Point p1, Point p2, Point q)
  {
    int a = p2.y - p1.y;
    int b = p1.x - p2.x;
    int c = p2.x*p1.y - p1.x*p2.y;
    int d = Math.abs(a*q.x + b*q.y + c);
    if (d == 0) return(0);
    else return(d / Math.sqrt(a*a + b*b));
  }

// this method is used to display the point set, the CH, and its diameter
  public void paint(Graphics g)
  {
    super.paint(g);

    g.setColor(Color.red);                   // draw points
    for (int i=0; i<points.size(); i++)
    {
      Point p = points.get(i);
      g.fillRect(p.x-1, p.y-1, 3, 3);
    }

    if (convHull.size() >= 3)                // draw convex hull
    {
      g.fillOval(origin.x-4, origin.y-4, 8, 8);

      g.setColor(Color.blue);                // CH color        
      Point p1 = convHull.get(0), p2;        // retrieve staring point
      for (int i=1; i<convHull.size(); i++)
      {
        p2 = convHull.get(i);
        g.drawLine(p1.x, p1.y, p2.x, p2.y);
        p1 = p2;
      }

      g.setColor(Color.green);               // shown anti-pair in green
      p1 = convHull.get(antiPair.x);
      p2 = convHull.get(antiPair.y);
      g.drawLine(p1.x, p1.y, p2.x, p2.y);
      double d = Math.sqrt((p1.x - p2.x)*(p1.x - p2.x) + 
              (p1.y - p2.y)*(p1.y - p2.y));
    
      g.drawOval((int)Math.round((p1.x+p2.x - d)/2.0), 
                 (int)Math.round((p1.y+p2.y - d)/2.0),
                 (int)Math.round(d), (int)Math.round(d)); 
    }
  }

// this method reoved duplicates from an array of points and returnes the
// reduced array as a linked list
  public LinkedList<Point> removeDuplicates(Point[] pts)
  {
    LinkedList<Point> ll = new LinkedList<Point>();
    ll.addLast(pts[0]);
    for (int i=1; i<pts.length; i++)
      if (! pts[i].equals(pts[i-1]))
        ll.addLast(pts[i]);
    return(ll);
  }

  public void mouseEntered(MouseEvent e) { }     // empty methods needed for 
  public void mouseExited(MouseEvent e) { }      // the MouseListener
  public void mouseReleased(MouseEvent e) { }    // interface implementation
  public void mouseClicked(MouseEvent e) { }
}