Estimate the probability that some subset of k out of n points uniformly randomly selected in the unit square forms a convex polygon; see http://math.stackexchange.com/questions/280648.

Question280648.java

import java.util.Random;

public class Question280648 {
    final static int ntrials = 1000000;
    final static Random random = new Random ();

    static class CombinationTraversal {
        int k,n;
        int [] combination;

        public CombinationTraversal (int n,int k) {
            this.k = k;
            this.n = n;
            combination = new int [k];
            initialize ();
        }

        public void initialize () {
            for (int i = 0;i < k;i++)
                combination [i] = k - i - 1;
        }

        boolean advance () {
            for (int i = 0;i < k;i++)
            if (combination [i] < n - i - 1) {
                combination [i]++;
                for (int j = i;j > 0;j--)
                    combination [j - 1] = combination [j] + 1;
                return true;
            }
            return false;
        }
    }

    public static void main (String [] args) {
        int npoints = Integer.parseInt (args [0]);
        int nvertices = Integer.parseInt (args [1]);
        double [] [] points = new double [npoints] [2];
        int [] indices = new int [nvertices];
        double [] [] vertices = new double [nvertices] [];
        
        CombinationTraversal traversal = new CombinationTraversal (npoints,nvertices);
        int count = 0;

        outer:
        for (int n = 0;n < ntrials;n++) {
            for (int i = 0;i < npoints;i++)
                for (int j = 0;j < 2;j++)
                    points [i] [j] = random.nextDouble ();

            traversal.initialize ();

            do {
                for (int i = 0;i < nvertices;i++)
                    vertices [i] = points [traversal.combination [i]];
                if (isConvex (vertices)) {
                    count++;
                    continue outer;
                }
            } while (traversal.advance ());
        }

        System.out.println (count / (double) ntrials);
    }

    static double [] [] triangle = new double [3] [];

    static boolean isConvex (double [] [] vertices) {
        CombinationTraversal traversal = new CombinationTraversal (vertices.length,3);

        do {
            for (int j = 0;j < 3;j++)
                triangle [j] = vertices [traversal.combination [j]];
            outer:
            for (int i = 0;i < vertices.length;i++) {
                for (int j = 0;j < 3;j++)
                    if (traversal.combination [j] == i)
                        continue outer;
                if (contains (triangle,vertices [i]))
                    return false;
            }
        } while (traversal.advance ());
        
        return true;
    }

    static boolean contains (double [] [] triangle,double [] point) {
        for (int i = 0;i < 3;i++) {
            double [] p1 = triangle [(i + 1) % 3];
            double [] p2 = triangle [(i + 2) % 3];
            double [] t1 = triangle [i];
            double [] t2 = point;

            if (((p1 [0] - p2 [0]) * (p1 [1] - t1 [1]) - (p1 [1] - p2 [1]) * (p1 [0] - t1 [0])) *
                ((p1 [0] - p2 [0]) * (p1 [1] - t2 [1]) - (p1 [1] - p2 [1]) * (p1 [0] - t2 [0])) < 0)
                return false;
        }
        
        return true;
    }
}