import java.io.* ;
import java.awt.*;
import java.awt.event.*;

class PointList {
  int x, y ;
  PointList next ;
  PointList (int x, int y, PointList next) {
    this.x = x ; this.y = y ; this.next = next ;
  }


  static boolean mem(int x, int y, PointList p) {
    for ( ; p != null ; p = p.next)
      if (p.x == x && p.y == y)
        return true ;
    return false ;
  }
  // Dessin

  private static final int T = 5;

  static void dessinerPoint(Graphics g,PointList p) {
    g.setColor(Color.black);
    g.fillOval(p.x-T,p.y-T,2*T,2*T);
  }

  static void dessiner(Graphics g, PointList p) {
    for ( ; p != null ; p = p.next) {
      dessinerPoint(g,p) ;
    }
  }

}

class PointReader {
  private Reader in ;

  PointReader (Reader in) {
    this.in = in ;
  }

  private static boolean number (int c) {
    return '0' <= c && c <= '9' ;
  }

  private int skip() throws IOException {
    int c ;
    
    while (!number((c=in.read())))
      if (c < 0)
        return c ;
    return c ;
  }

  int readInt() throws IOException {
    int c = skip () ;
    if (c < 0)
      return -1 ;

    int r = c - '0' ;

    while((c = in.read()) >= 0) {
      if (number(c)) {
        r = 10*r + c - '0' ;
      } else
        return r ;
    }
    return r ;
  }

  PointList next() {
    try {
      int h = readInt() ;
      if (h < 0)
        return null ;
      
      int v = readInt() ;
      if (v < 0)
        return null ;

      return new PointList(h,v,null) ;
    } catch (IOException e) {
      System.err.println("Malaise: " + e.getMessage ()) ;
      System.exit(2) ;
      return null ;
    }
  }
}

class ConvexFrame extends Frame implements WindowListener {
  MonCanvas fenetreDessin;
  Label info;
	
  // Constructeur de la fenetre
  ConvexFrame(String s, PointReader pr) {
    super(s);
    setLayout(new BorderLayout());
    fenetreDessin = new MonCanvas(this, pr);
    add(fenetreDessin);
    Panel p = new Panel();

    Button bQuit = new Button("Quit");
    bQuit.addActionListener(new ActionListener() {
        public void actionPerformed(ActionEvent e) {
          System.exit(0);
        }
      });
	
    // Creation du label information qui servira
    // a afficher les coordonnees des points
    info = new Label();
    add("South",info);

    // On cree un panneau en haut pour mettre des boutons
    Panel pHaut = new Panel();
    pHaut.setLayout(new FlowLayout());
	
    pHaut.add(bQuit);
    add("North",pHaut);

    addWindowListener(this);
    setLocation(100,100) ;
    setSize(500,500);
    setVisible(true);
  }	
    
  // Affiche une chaine de caracteres
  void afficheInfo(String s) {
    info.setText(s);
  }
	
  // Methodes de gestion pour une fenetre
	
  public void windowOpened(WindowEvent e) {}
  public void windowClosed(WindowEvent e) {}
  public void windowIconified(WindowEvent e) {}
  public void windowDeiconified(WindowEvent e) {}
  public void windowActivated(WindowEvent e) {}
  public void windowDeactivated(WindowEvent e) {}
	
  // Methode appele lors de l appui sur l icone de fermeture de 
  // la fenetre
  public void windowClosing(WindowEvent e) {
    dispose();
    System.exit(0);
  }
}


// Fenetre de dessin
class MonCanvas extends Canvas implements MouseListener {
  Convexe cvx = new Convexe () ;
  PointList pts = null ;
  PointReader pr ;
  ConvexFrame fenetre;


  MonCanvas(ConvexFrame gf, PointReader pr) {
    fenetre = gf;
    this.pr = pr ;
    addMouseListener(this);
  }
    
  // Methode appelee pour redessiner tout le Canvas
  public void paint(Graphics gr) {
    PointList.dessiner(gr, pts);
    cvx.dessiner(gr) ;
  }
    



  // Liste des methodes du MouseListener

  public void mouseClicked(MouseEvent e) {
    int x, y ;
    if (pr == null) {
      x = e.getX() ;
      y = e.getY() ;
    } else {
      PointList p = pr.next() ;
      if (p != null) {
        x = p.x ;
        y = p.y ;
      } else {
        return ;
      }
    }

    if (!PointList.mem(x, y, pts)) {
      Graphics gr = getGraphics();
      System.out.println(x + " " + y) ;
      pts = new PointList(x, y, pts) ;      
      PointList.dessinerPoint(gr, pts) ;
      if (cvx.etendre(pts)) repaint() ;
    }
  }    

  public void mousePressed(MouseEvent e) {}
  public void mouseReleased(MouseEvent e) {}

  // On recupere le focus dans le Canvas des que la souris entre
  // dans celui-ci
  public void mouseEntered(MouseEvent e) {
    requestFocus();
  }
  public void mouseExited(MouseEvent e) {}
}

class Convexe {
  PointList cvx ; // Liste des sommets. Attention, c'est une liste bouclée

  // Travail sur l'enveloppe convexe.

  // Renvoie un entier r 
  //    - r < 0  -> q est à droite du vecteur p1 p2
  //    - r > 0  -> q est à gauche du vecteur p1 p2
  //    - r == 0 -> q p1 p2 alignés

  static private int det(PointList q, PointList p1, PointList p2) {
    int r =
      (q.y - p1.y) * (p2.x - p1.x) - (q.x - p1.x) * (p2.y - p1.y) ;
    return r ;
  }


  // Fabrication d'un triangle comme liste bouclée de trois points
  static private PointList triangle (PointList p1, PointList p2, PointList p3) {
    PointList r3 = new PointList(p3.x, p3.y, null) ;
    PointList r2 = new PointList(p2.x, p2.y, r3) ;
    PointList r1 = new PointList(p1.x, p1.y, r2) ;
    r3.next = r1 ;
    return r1 ;
  }



  private final static int NONE=0, LIGHT=1, SHADOW=2 ;

  // Étendre l'enveloppe convexe (liste bouclée cvx)
  // Le point ajouté est le premier de l'argument p
  // etendre renvoie un booléen, qui indique un changement de l'enveloppe.

 boolean etendre(PointList p) {
    if (cvx == null) {
      PointList p1 = p ;
      if (p1.next == null)  return false ;
      PointList p2 = p1.next ;
      if (p2.next == null) return false ;
      PointList p3 = p2.next ;
      if (det(p1, p2, p3) < 0) {
        cvx = triangle(p1,p2,p3) ;
      } else {
        cvx = triangle(p1,p3,p2) ;
      }
      return true ;
    } else {
      PointList first = null , last = null ;
      PointList q ;
      int prev = NONE ;
      int edge ;

      // Recherche des transitions entre ombre et lumière
      q = cvx ;
      do {
        if (det(p, q, q.next) >= 0) {
          edge = LIGHT ;
          if (prev == SHADOW) first = q ;
        } else {
          edge = SHADOW ;
          if (prev == LIGHT) last = q ;
        }
        prev = edge ;
        q = q.next ;
      } while (q != cvx) ;
      // Examen de l'arc issu du premier point
      if (det(p, q, q.next) >= 0) {
        if (prev == SHADOW) first = q ;
      } else {
        if (prev == LIGHT) last = q ;
      }

      // Le point ajouté est à l'intérieur
      if (last == null) return false ;

      // Suppression des sommets éclairés, et ajout du nouveau point
      cvx = new PointList(p.x, p.y, last) ;
      first.next = cvx ;
      return true ;
    }
  }

  // Dessin des arcs
  static private void arc(Graphics g, PointList q) {
     g.drawLine(q.x, q.y, q.next.x, q.next.y) ;
  }
  void dessiner(Graphics g) {
    if (cvx == null) return ;
    PointList q=cvx ;
    do {
      arc(g,q) ;
      q = q.next ;
    } while (q != cvx) ;
  }

  public static void main(String arg[]) {
    PointReader pr=null;
    if (arg.length == 1) {
     try {
       pr = new PointReader (new FileReader (arg[0])) ;
     } catch (FileNotFoundException e) {
       System.err.println("Malaise : " + e.getMessage()) ;
       System.exit(2) ;
     }
    } else if (arg.length != 0) {
      System.err.println("usage : java Convexe [file]") ;
      System.exit(2) ;
    }
    ConvexFrame f = new ConvexFrame("Enveloppe convexe", pr);
  }
}