挑战程序设计竞赛（算法和数据结构）——16.12凸包（安德鲁算法）的JAVA实现

题目与思路：



代码：

import java.util.*;
//数据结果套数据结构时，需要一层一层初始化
public class ConvexHull {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        Vector S = new Vector();
        for (int i=0;i v1 = new Vector();
        Vector v2 = new Vector();
        Vector v3 = new Vector();
        GraghBasic.Polygon u = new GraghBasic.Polygon(v1);
        GraghBasic.Polygon l = new GraghBasic.Polygon(v2);

        if(s.P.size()<3)return s;//不足三位的就不是多边形
        s = mySort(s);//对s中的元素进行排序
        u.P.add(s.P.elementAt(0));
        u.P.add(s.P.elementAt(1));
        l.P.add(s.P.elementAt(s.P.size()-1));
        l.P.add(s.P.elementAt(s.P.size()-2));

        //构建凸包上部
        for (int i=2;i=2 && CounterClockwise.myCounterClockwise(u.P.elementAt(n-2), u.P.elementAt(n-1), s.P.elementAt(i))=="COUNTER_CLOCKWISE";n--){
                u.P.remove(u.P.size()-1);
            }
            u.P.add(s.P.elementAt(i));
        }

        //构建凸包下部
        for (int i=s.P.size()-3;i>=0;i--){
            for (int n=l.P.size();n>=2 && CounterClockwise.myCounterClockwise(l.P.elementAt(n-2), l.P.elementAt(n-1), s.P.elementAt(i))=="COUNTER_CLOCKWISE";n--){
                l.P.remove(l.P.size()-1);
            }
            l.P.add(s.P.elementAt(i));
        }

        GraghBasic.Polygon t = new GraghBasic.Polygon(v3);
        for (int k=l.P.size()-1;k>=1;k--){
            t.P.add(l.P.elementAt(k));
        }
        for (int k=u.P.size()-1;k>=1;k--){
            t.P.add(u.P.elementAt(k));
        }
        return t;
    }

    public static GraghBasic.Polygon mySort(GraghBasic.Polygon s){
        int n = s.P.size();
        for (int i=0;is.P.elementAt(j).x){
                    Collections.swap(s.P, i, j);
                }
                else if(s.P.elementAt(i).x==s.P.elementAt(j).x && s.P.elementAt(i).y>s.P.elementAt(j).y){
                    Collections.swap(s.P, i, j);
                }
            }
        }
        return s;
    }
}

输入：

7
2 1
0 0
1 2
2 2
4 2
1 3
3 3

输出：

5
0.0 0.0
2.0 1.0
4.0 2.0
3.0 3.0
1.0 3.0