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

public class ClosestPair extends JFrame implements ActionListener
{
  class ClosestPointPair
  {
    double d;                               // shortest distance
    int p;                                  // is between points #p and #q
    int q;
    public void setPair(int p, int q, double d)
    {
      this.p = p;
      this.q = q;
      this.d = d;
    }
    public ClosestPointPair()
    {
      setPair(-1, -1, Double.MAX_VALUE);
    }
    public ClosestPointPair(int p, int q, double d)
    {
      setPair(p, q, d);
    }
    public ClosestPointPair(ClosestPointPair pair)
    {
      setPair(pair.p, pair.q, pair.d);
    }
  }
  Point[] points;                           // storage for points
  Integer[] ptsX;                           // point indices sorted wrt X-coord.
  int n = 10;                               // # of points
  ClosestPointPair cp;                      // storage for the closest pair

  LinkedList<Integer> vertLines = new LinkedList<Integer>();  
                                            // storage for vertical lines
  JPanel topPanel, drawPanel;               // graphics stuff
  JTextField textField;
  JCheckBox checkBox;
  JButton button;
  int width, height, shift;

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

  public ClosestPair()
  {
    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("Closest Pair of Points");

    topPanel = new JPanel();                // building GUI
    topPanel.setBackground(Color.orange);   
    topPanel.setLayout(new FlowLayout());
    textField = new JTextField("10", 3);
    button = new JButton("Start Over");
    topPanel.add(new JLabel("# of points: "));
    topPanel.add(textField);
    topPanel.add(new JLabel("           "));
    topPanel.add(button);
    topPanel.add(new JLabel("           "));
    checkBox = new JCheckBox("show lines", true); 
    checkBox.setBackground(Color.orange);
    topPanel.add(checkBox);
    topPanel.doLayout();
    drawPanel = new JPanel();
    drawPanel.setBackground(new Color(0xffffcc));

    Container pane = getContentPane();
    pane.setLayout(new BorderLayout());
    pane.add(topPanel, BorderLayout.NORTH); 
    pane.add(drawPanel, BorderLayout.CENTER);

    button.addActionListener(this);
    textField.addActionListener(this);
    checkBox.addActionListener(this);
    setVisible(true);
  }
        
  public void actionPerformed(ActionEvent e) 
  { 
    if (e.getSource() == button || e.getSource() == textField)
    {
      n = Integer.parseInt(textField.getText()); // retrieve the # of points
      shift = topPanel.getHeight();              // height of the control panel
shift = 70;
      height = drawPanel.getHeight();            // dimensions of the draw panel
      width = drawPanel.getWidth();
      points = generatePoints(n, width, height); // generate new points
      cp = computeClosestPair(points);           // compute the closest pair
    }
    repaint();                                 // update the display
  }

  // this method provides necessary initialization for the algorithm
  // and calls the recursive method for finding a closest pair
  public ClosestPointPair computeClosestPair(Point[] pts)
  {
    ptsX = new Integer[n];                     // sorted X coords of points
    for (int i=0; i<n; i++)                    // array initialization 
      ptsX[i] = new Integer(i);
    Arrays.sort(ptsX, new Comparator<Integer>() // sort the X coords
    {
      public int compare(Integer i1, Integer i2) // comparator for sorting
      {
        int i = i1.intValue();
        int j = i2.intValue();
        if (points[i].x==points[j].x) return(0);
        else if (points[i].x < points[j].x)
          return(-1);
        else return(1);
      }
    });

    return(recursiveClosestPair(0, n-1));      // recursive call
  }

  // this is a recursive method that finds closest pair of points
  // whose indices in the ptsX array are between start and finish (incl.)
  public ClosestPointPair recursiveClosestPair(int start, int finish)
  {
    if (start >= finish) return(new ClosestPointPair());
    if (start == finish-1)                     // termination conditions
    {
      double dist = distance(points[start], points[finish]);
      return(new ClosestPointPair(start, finish, dist));
    } 
 
    int midIndex = (start + finish)/2;         // vertical line separator
    int vertLine = points[((Integer) ptsX[midIndex]).intValue()].x;
    vertLines.add(new Integer(vertLine));      // save it (for display)

    ClosestPointPair leftPair = recursiveClosestPair(start, midIndex);
    ClosestPointPair rightPair = recursiveClosestPair(midIndex+1, finish);

    ClosestPointPair pair = new ClosestPointPair(leftPair);
    if (leftPair.d > rightPair.d)              // compute d=min{dist_L, dist_R}
      pair.setPair(rightPair.p, rightPair.q, rightPair.d);

    int[] yZone = new int[n];                  // construct the vertical
    int yZoneSize = 0;                         // zone of width d
    for (int i=0; i<n; i++)                    // about the separating line
    {                                          // the points of this Y-zone
      int x = points[i].x;                     // will be automatically
      if ((vertLine - pair.d <= x) && (x <= vertLine + pair.d)) 
        yZone[yZoneSize++] = i;                // sorted wrt Y-coord.
    }

    for (int i=0; i<yZoneSize; i++ )           // loop over the points in
    {                                          // Y-zone
      Point p = points[yZone[i]];              // retrieve current point
      for (int j=i+1; j<yZoneSize; j++)        // check points within dist d
      {                                        // from p (at most 5 points)
        Point q = points[yZone[j]];
        double dist = distance(p, q);
        if (dist < pair.d)
          pair.setPair(yZone[i], yZone[j], dist);
        else
          break;
      }
    }

    return(pair);                              // return closest pair
  }

  public double distance(Point p, Point q)     // compute the (Euclidean) dist
  {                                            // between two points
    return(Math.sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)));
  }

  public void paint(Graphics g)                // graphics stuff
  {
    super.paint(g);                            // needed for displaying the GUI

    if (points==null) return;
    g.setColor(Color.red);                     // draw points in red
    for (int i=0; i<n; i++)
      g.fillRect(points[i].x-1, points[i].y-1, 3, 3);

    if (cp.p >= 0 && cp.q >= 0)                // draw the closest pair in blue
    {
      g.setColor(Color.blue);
      g.fillRect(points[cp.p].x-2, points[cp.p].y-2, 5, 5);
      g.fillRect(points[cp.q].x-2, points[cp.q].y-2, 5, 5);
      g.drawLine(points[cp.p].x, points[cp.p].y, 
                 points[cp.q].x, points[cp.q].y);
    }

    if (checkBox.isSelected())                 // draw the vertical lines
    for (int i=0; i<vertLines.size(); i++)
    {
      int x = vertLines.get(i).intValue();
      g.setColor(Color.green);
      g.drawLine(x, shift, x, height+shift);
      g.setColor(Color.black);
//      g.drawString((i++)+"", x, shift+10);
      g.drawString(i+"", x, shift+10);
    }
//g.drawLine(0,shift,width,height+shift);
  }

  // this method generates m random points and deletes duplicates
  // the final number of points might be less than m
  public Point[] generatePoints(int m, int w, int h)
  {
    vertLines.clear();
    Point[] pts = new Point[n];               // storage for points
    Calendar cal = Calendar.getInstance();    // set up the random numbers
    long seed = cal.getTimeInMillis();        // seed for the generator
    Random generator = new Random(seed);      // random numbers generator
    for (int i=0; i<m; i++)
    {
      int x = generator.nextInt(w);           // create a random point
      int y = generator.nextInt(h)+shift;     // .. its Y-coordinate 
      pts[i] = new Point(x, y);               // ... and add it to the list
    }
    
    // check and remove possible duplicates
    Arrays.sort(pts, new Comparator<Point>()  // MergeSort the points 
    {                                         // wrt to their Y-coords
      public int compare(Point p1, Point p2)     
      {                                          
        if ((p1.x==p2.x) && (p1.y==p2.y))
          return(0);
        else if ((p1.y < p2.y) || ((p1.y==p2.y) && (p1.x < p2.x)))
          return(-1);              
        else return(1);
      }
    });

    LinkedList<Point> ll = new LinkedList<Point>(); // remove duplicates from
    ll.addLast(pts[0]);                       // the sorted array 
    for (int i=1; i<pts.length; i++)
      if (! pts[i].equals(pts[i-1]))
        ll.addLast(pts[i]);
    n = ll.size();                            // update n
    return(ll.toArray(new Point[ll.size()]));
  }
}