import java.awt.*;
        import java.awt.Color;
        import java.awt.Graphics;
        import java.awt.event.*;
        import java.awt.event.WindowAdapter;
        import java.awt.event.WindowEvent;
        import java.util.List;
        import java.util.Vector;

        class Convex extends Frame implements ActionListener, TextListener, MouseMotionListener{

            static Convex frm = new Convex();
            static Button btn = new Button("Send");
            static TextArea txa = new TextArea("請輸入要幾個點");
            //static TextArea txa1 = new TextArea("Convex Hull");
            static Label lab = new Label();
            static Label lab1 = new Label("Convex Hull");
            int amount;

            private static class Vertex {
                public int x;
                public int y;


                public Vertex(int x, int y) {
                    this.x = x;
                    this.y = y;
                }
            }
            /*----------------------------------------------*/




            public static void main(String args[]){
                btn.addActionListener(frm);
                txa.addTextListener(frm);
                frm.addMouseMotionListener(frm);

                frm.setLayout(null);
                frm.setTitle("Convex Hull");
                btn.setBounds(425,500,75,50);
                txa.setBounds(200,500,225,50);
                lab1.setBounds(100,30,300,40);
                lab1.setBackground(Color.yellow);
                lab.setBounds(30,500,190,50);

                frm.setSize(500,550);
                frm.add(btn);
                frm.add(txa);
                frm.add(lab1);
                frm.add(lab);
                frm.setVisible(true);


                frm.addWindowListener(new WindowAdapter(){
                    public void windowClosing(WindowEvent e){
                        frm.dispose();
                    }
                });
            }




            public void actionPerformed(ActionEvent e){
                Graphics g = getGraphics();
                update(g);
            }


            public void textValueChanged(TextEvent e){

                amount = Integer.valueOf(txa.getText());
            }


            public void mouseMoved(MouseEvent e){
                lab.setText("座標：("+e.getX()+","+e.getY()+")");
            }


            public void mouseDragged(MouseEvent e){
                lab.setText("座標：("+e.getX()+","+e.getY()+")");
            }
            /*-----------------------------------------------*/




            public void paint(Graphics g){

                int x[] = new int[amount];
                int y[] = new int[amount];
                List<Vertex> vertices = new Vector<Vertex>();


                for(int i=0; i<x.length; i++){

                    x[i] = (int)(Math.random()*441)+30;
                    y[i] = (int)(Math.random()*405)+75;

                    Vertex v = new Vertex(x[i], y[i]);
                    vertices.add(v);
                    g.setColor(Color.red);
                    g.fillOval(x[i], y[i], 5, 5);
                }


                long begin = System.currentTimeMillis();
                List<Vertex> polygon = convexhull(vertices);
                long elapsed = System.currentTimeMillis()-begin;
                double seconds = elapsed/1000.0;


                for(int i=1; i<polygon.size(); i++) {
                    g.setColor(Color.black);
                    g.drawLine(polygon.get(i-1).x, polygon.get(i-1).y, polygon.get(i).x, polygon.get(i).y);
                }

                g.setColor(Color.black);
                g.drawLine(polygon.get(0).x, polygon.get(0).y, polygon.get(polygon.size()-1).x, polygon.get(polygon.size()-1).y);

                System.out.printf("耗費了 %f 秒\n", seconds);
            }
            /*-----------------------------------------------*/




            public static List<Vertex> convexhull(List<Vertex> vertices){
                List<Vertex> polygon = new Vector<Vertex>();
                int left, right;
                int dxs,dys;
                int dxc,dyc;
                int dxt,dyt;
                int lqc,lqt;
                int compareResult;
                int x;
                Vertex current = null;
                Vertex next = null;


                left = vertices.get(0).x;
                right = vertices.get(0).x;
                for(int i=1; i<vertices.size(); i++){

                    x = vertices.get(i).x;
                    if(x<left) left = x;
                    if(x>right) right = x;
                }


                for(Vertex v : vertices){

                    if(v.x==left && (current==null || v.y>current.y))
                        current = v;

                }


                polygon.add(current);




                dys = 1;  dxs = 0;
                while(current.x<=right){
                    dyc = -1;  dxc = 0;  lqc = 0;
                    for(Vertex v : vertices){
                    //依序把 vertices 加入 v
                        if(v.x>=current.x){
                            dyt = v.y - current.y;
                            dxt = v.x - current.x;


                            if(compareSlope(dyt, dxt, dys, dxs) == -1){
                                compareResult = compareSlope(dyt,dxt,dyc,dxc);
                                lqt = dyt*dyt+dxt*dxt;

                                if(compareResult>=0)
                                    if(compareResult>0 || lqt>lqc){
                                        next = v;
                                        dyc = dyt;
                                        dxc = dxt;
                                        lqc = lqt;
                                    }
                            }
                        }
                    }

                    if(next == null) break;

                    dys = dyc;
                    dxs = dxc;
                    polygon.add(next);
                    vertices.remove(next);
                    current = next;
                    next = null;
                }



                dys = 1;  dxs = 0;
                while(current.x>left){
                    dyc = -1;  dxc = 0;  lqc = 0;
                    for(Vertex v : vertices){
                        if(v.x<current.x){
                            dyt = v.y - current.y;
                            dxt = v.x - current.x;

                            if(compareSlope(dyt, dxt, dys, dxs) == -1){
                                compareResult = compareSlope(dyt, dxt, dyc, dxc);
                                lqt = dyt*dyt+dxt*dxt;  //計算長度平方

                                if(compareResult>=0)
                                    if(compareResult>0 || lqt>lqc){
                                        next = v;
                                        dyc = dyt;
                                        dxc = dxt;
                                        lqc = lqt;
                                    }
                            }
                        }
                    }

                    if(next == null) break;
                    dys = dyc;
                    dxs = dxc;
                    polygon.add(next);
                    current = next;
                    next = null;
                }

                return polygon;
                //回傳我們找到的最外圍的點
            }





            public static int compareSlope(int dy2, int dx2, int dy1, int dx1){
                if(dx2!=0 && dx1!=0){

                     double test = dy2*dx1-dy1*dx2;
                     return (int)Math.signum(test);

                }

                else{

                    if(dx2!=0 || dx1!=0){
                        if(dx2 == 0){

                            return dy2>=0 ? 1 : -1;
                        }
                        else{

                            return dy1>=0 ? -1 : 1;
                        }
                    }

                    else{

                        if(dy2>=0){

                            return dy1>=0 ? 0 : 1;
                        }
                        else{

                            return dy1>=0 ? -1 : 0;
                        }
                    }
                }
            }
            /*-----------------------------------------------*/
        }