程序代码：

package Tubao;

import java.applet.Applet;
import java.awt.Color;
import java.awt.Graphics;
import java.util.Random;

public class Tubao extends Applet {
    int i, j, n, x[], y[];

    public void paint(Graphics g) {
        // TODO Auto-generated method stub
        // super.paint(g);
        Random r = new Random(1759);
        // n = Math.abs(r.nextInt(14)) + 1; // 随机产生点的个数（1~15）
        n = 5;
        x = new int[n];
        y = new int[n];

        // 随机产生x轴和y轴坐标
        for (i = 0; i < n; i++) {
            x[i] = Math.abs(r.nextInt(750)) + 50; // 范围：50~800
            y[i] = Math.abs(r.nextInt(450)) + 50; // 范围：50~500
            System.out.println("A" + (i + 1) + "(" + x[i] + "," + y[i] + ")");
        }

        // 描点
        g.setColor(Color.red);
        for (i = 0; i < n; i++) {
            g.drawOval(x[i] - 5, y[i] - 5, 10, 10);
            g.fillOval(x[i] - 5, y[i] - 5, 10, 10);
            g.setColor(Color.blue);
            g.drawString("A" + (i + 1) + "(" + x[i] + "," + y[i] + ")",
                    x[i] - 25, y[i] + 20);
        }

        // 查找极点
        for (i = 0; i < n - 1; i++) {
            System.out.println("A" + (i + 1));
            for (j = 0; j < n; j++) {
                int count1 = 0, count2 = 0, count3 = 0; // 计数器，分别统计直线两侧和直线上的点的个数
                int m = 0, t[] = new int[n + 1]; // t[]用来存放直线上点的下标
                int a = y[j] - y[i];
                int b = x[j] - x[i];
                int c = x[i] * y[j] - y[i] * x[j];

                // 检查每个点相对于直线的位置
                for (int temp = 0; temp < n; temp++) {
                    if (temp != i && temp != j) {
                        if ((a * x[temp] + b * y[temp] - c) > 0) {
                            count1++;
                        } else if ((a * x[temp] + b * y[temp] - c) < 0) {
                            count2++;
                        } else {
                            count3++;
                            t[m++] = temp;
                        }
                    }
                }

                // 判断连线并连线
                g.setColor(Color.blue);
                if ((count1 == 0 || count2 == 0) && (count3 == 0)) {
                    g.drawLine(x[i], y[i], x[j], y[j]);
                    try {
                        Thread.sleep(1500); // 停顿1.5s
                    } catch (InterruptedException e) {

                    }
                } else if ((count1 == 0 || count2 == 0) && (count3 != 0)) {
                    t[m++] = i;
                    t[m] = j;

                    int d, dmax = 0;
                    int tp, tq, index1 = 0, index2 = 0;

                    // 取直线上距离最大的两点为极点
                    for (int p = 0; p < t.length - 1; p++) {
                        tp = t[p];
                        for (int q = p + 1; q < t.length; q++) {
                            tq = t[q];
                            d = (x[tp] - x[tq]) * (x[tp] - x[tq])
                                    + (y[tp] - y[tq]) * (y[tp] - y[tq]);
                            if (d > dmax) {
                                dmax = d;
                                index1 = tp;
                                index2 = tq;
                            } else
                                continue;

                        }
                    }
                    g.drawLine(x[index1], y[index1], x[index2], y[index2]);
                    try {
                        Thread.sleep(1500); // 停顿1.5s
                    } catch (InterruptedException e) {

                    }
                } else
                    continue;

            }

        }

    }

}