import java.awt.geom.Path2D;
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class Tests {

    final int MAXC = (int) 1e6;
    final int MAXN = 2000;

    class Test {
        int[] x;
        int[] y;
        int[] xg;
        int[] yg;
        String comment;
    }

    int testNumber;
    Random rnd = new Random(239017);
    PrintWriter testComments;

    private void printTest(Test test) throws IOException {
        testNumber++;
        new File("../tests").mkdir();
        PrintWriter out = new PrintWriter(new File(String.format("../tests/%02d", testNumber)));
        assert test.x.length == test.y.length;
        assert test.xg.length == test.yg.length;
        out.println(test.x.length);
        for (int i = 0; i < test.x.length; i++)
            out.println(test.x[i] + " " + test.y[i]);
        out.println(test.xg.length);
        for (int i = 0; i < test.xg.length; i++)
            out.println(test.xg[i] + " " + test.yg[i]);
        out.close();
        testComments.println("Test " +testNumber + ": "+test.comment);
    }

    private void print(Test... tests) throws IOException {
        for (Test test : tests) {
            printTest(test);
        }
    }

    private void getRandomPoints(int[] x, int[] y, int[] xg, int[] yg) {
        int maxCx = Integer.MIN_VALUE;
        int maxCy = Integer.MIN_VALUE;
        int minCx = Integer.MAX_VALUE;
        int minCy = Integer.MAX_VALUE;
        for (int i = 0; i < x.length; i++){
            maxCx = Math.max(maxCx, x[i]);
            minCx = Math.min(minCx, x[i]);
            maxCy = Math.max(maxCy, y[i]);
            minCy = Math.min(minCy, y[i]);
        }
        int dx = maxCx - minCx;
        int dy = maxCy - minCy;
        maxCx = Math.min((int) (maxCx + 0.1 * dx), MAXC);
        maxCy = Math.min((int) (maxCy + 0.1 * dy), MAXC);
        minCx = Math.max((int) (minCx - 0.1 * dx), -MAXC);
        minCy = Math.max((int) (minCy - 0.1 * dy), -MAXC);
        assert xg.length == yg.length;
        for (int i = 0; i < xg.length; i++) {
            xg[i] = rnd.nextInt(maxCx - minCx + 1) + minCx;
            yg[i] = rnd.nextInt(maxCy - minCy + 1) + minCy;
            while (SharedGeom.checkInside(x, y, xg[i], yg[i])) {
                xg[i] = rnd.nextInt(maxCx - minCx + 1) + minCx;
                yg[i] = rnd.nextInt(maxCy - minCy + 1) + minCy;
            }
        }
    }

    int getRandSeed(int n, int m, int maxC, String name) {
        return ((n * 239017 + m) * 17239 + maxC) * 1000000009 + name.hashCode();
    }

    void GenerateTest(int n,int m,int maxC,PolygonGenerator generator, int seed) throws IOException {
        System.err.printf("Generating polygon for test %d, n = %d, m = %d, maxC = %d, Generator=%s, seed = %d\n",
                testNumber+1, n, m, maxC, generator.Name(), seed);
        Test test = new Test();
        test.x = new int[n];
        test.y = new int[n];
        test.xg = new int[m];
        test.yg = new int[m];
        test.comment= String.format("n = %d, m = %d, maxC = %d, Generator=%s, seed = %d",
                n, m, maxC, generator.Name(), seed);
        generator.generate(test.x, test.y, maxC, maxC, new Random(seed));
        int ptr = 0;
        int[] nx = new int[n];
        int[] ny = new int[n];
        nx[0] = test.x[0];
        ny[0] = test.y[0];
        nx[1] = test.x[1];
        ny[1] = test.y[1];
        ptr = 2;
        for (int i = 2; i < n; i++){
            int dx1 = nx[ptr-1] - nx[ptr-2];
            int dx2 = test.x[i] - nx[ptr-1];
            int dy1 = ny[ptr-1] - ny[ptr-2];
            int dy2 = test.y[i] - ny[ptr-1];
            if ((long)dx1 * (long)dy2 - (long)dx2 * (long)dy1 != 0)
                ptr++;
            else {
                System.err.printf("Remove point (%d, %d) from line (%d, %d)--(%d, %d)\n", nx[ptr-1], ny[ptr-1], nx[ptr-2], ny[ptr-2], test.x[i], test.y[i]);
            }
            nx[ptr-1] = test.x[i];
            ny[ptr-1] = test.y[i];
        }
        for (int i = 0; i < ptr; i++){
            test.x[i] = nx[i];
            test.y[i] = ny[i];
        }
        test.x = Arrays.copyOf(nx, ptr);
        test.y = Arrays.copyOf(ny, ptr);
        System.err.printf("Generating points\n");
        getRandomPoints(test.x, test.y, test.xg, test.yg);
        print(test);
    }

    class TestGenerator {
        int n,m,maxCs;
        PolygonGenerator generator;
        TestGenerator(int n,int m,int maxCs, PolygonGenerator generator){
            this.n = n;
            this.m = m;
            this.maxCs = maxCs;
            this.generator = generator;
        }
    }

    void run() throws IOException {
        testComments = new PrintWriter(new File("tests.comments"));
        {
            Test test = new Test();
            test.x = new int[]{0, -3, 0, 3};
            test.y = new int[]{0, -3, -6, -3};
            test.xg = new int[]{-8, -2, 2};
            test.yg = new int[]{0, 0, -1};
            test.comment = "Hand sample test";
            print(test);
        }

        ArrayList<TestGenerator> gens = new ArrayList<TestGenerator>();


        gens.add(new TestGenerator(10, 10, 1000, new CrossReverseGenerator()));
        gens.add(new TestGenerator(10, 10, 1000, new AngleGenerator()));
        gens.add(new TestGenerator(10, 100, 1000, new CrossReverseGenerator()));
        gens.add(new TestGenerator(10, 100, 1000, new AngleGenerator()));
        gens.add(new TestGenerator(10, 2000, 1000, new CrossReverseGenerator()));
        gens.add(new TestGenerator(10, 2000, 1000, new AngleGenerator()));
        gens.add(new TestGenerator(10, 2000, MAXC, new CrossReverseGenerator()));
        gens.add(new TestGenerator(10, 2000, MAXC, new AngleGenerator()));

        gens.add(new TestGenerator(100, 2000, 1000, new CrossReverseGenerator()));
        gens.add(new TestGenerator(100, 2000, 1000, new AngleGenerator()));
        gens.add(new TestGenerator(100, 2000, 1000, new SpiralGenerator()));
        gens.add(new TestGenerator(100, 2000, MAXC, new CrossReverseGenerator()));
        gens.add(new TestGenerator(100, 2000, MAXC, new AngleGenerator()));
        gens.add(new TestGenerator(100, 2000, MAXC, new SpiralGenerator()));


        gens.add(new TestGenerator(2000, 2000, MAXC, new CrossReverseGenerator()));
        gens.add(new TestGenerator(2000, 2000, MAXC, new AngleGenerator()));
        gens.add(new TestGenerator(2000, 2000, MAXC, new SpiralGenerator()));
        gens.add(new TestGenerator(2000, 2000, MAXC-2, new EllipseGenerator())); // MAXC -1 for fixing spped of generation
        gens.add(new TestGenerator(2000, 2000, MAXC, new KochGenerator()));
        gens.add(new TestGenerator(2000, 2000, 10000, new CrossReverseGenerator()));
        gens.add(new TestGenerator(2000, 2000, 10000, new AngleGenerator()));
        gens.add(new TestGenerator(2000, 2000, 10000, new SpiralGenerator()));


        // 5000 will be converted to exactly 2000
        gens.add(new TestGenerator(5000, 5000, MAXC, new CrossReverseGenerator())); 
        gens.add(new TestGenerator(5000, 5000, MAXC, new AngleGenerator())); 
        gens.add(new TestGenerator(5000, 5000, MAXC, new SpiralGenerator())); 
        gens.add(new TestGenerator(4900, 5000, MAXC, new EllipseGenerator()));  // failed randseed with 5000
        gens.add(new TestGenerator(5000, 5000, MAXC, new KochGenerator()));  

        for (TestGenerator gen : gens){
            int n = gen.n;
            int m = gen.m;
            int maxC = gen.maxCs;
            PolygonGenerator generator = gen.generator;
            int tn = Math.min(MAXN, n - rnd.nextInt(n / 10));
            int tm = Math.min(MAXN, m - rnd.nextInt(m / 10));
            int seed = getRandSeed(n, m, maxC, generator.shortName());
            GenerateTest(tn, tm, maxC, generator, seed);
        }                                                                  
        GenerateTest(1818, 1982, 1000000, new SpiralGenerator(), 258839671);
        testComments.close();
    }


    public static void main(String[] args) {
        try {
            new Tests().run();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(239);
        }
    }
}

