import java.io.*;
import java.util.*;

public class TestGen {
    private static int nTests = 0;
    private static Random random = new Random(42);

    private static void write(List<Point[]> triangles, String descEn, String descRu) {
        try {
            PrintWriter out = new PrintWriter(String.format("%02d", ++nTests));
            out.println(triangles.size());
            for (Point[] t : triangles) {
                boolean first = true;
                for (Point p : t) {
                    if (!first) {
                        out.print(" ");
                    }
                    first = false;
                    out.print(p.x + " " + p.y);
                }
                out.println();
            }
            out.close();

            PrintWriter descEnP = new PrintWriter(new OutputStreamWriter(
                    new FileOutputStream("test-en.desc", nTests > 1), "cp1251"));
            descEnP.printf("%02d - %s%n", nTests, descEn);
            descEnP.close();

            PrintWriter descRuP = new PrintWriter(new OutputStreamWriter(
                    new FileOutputStream("test-ru.desc", nTests > 1), "cp1251"));
            descRuP.printf("%02d - %s%n", nTests, descRu);
            descRuP.close();
        }  catch (IOException ex) {
            ex.printStackTrace();
        }
    }

    private static class Point {
        public final int x, y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public Point subtract(Point arg) {
            return new Point(x - arg.x, y - arg.y);
        }
        public Point add(Point arg) {
            return new Point(x + arg.x, y + arg.y);
        }
        public String toString() {
            return "(" + x + "; " + y + ")";
        }
        public int smul(Point arg) {
            return x * arg.x + y * arg.y;
        }
        public int vmul(Point arg) {
            return x * arg.y - y * arg.x;
        }
        public Point multiply(int t) {
            return new Point(x * t, y * t);
        }
    }

    private static boolean leftTurn(Point base, Point left, Point right) {
        return (left.x - base.x) * (right.y - base.y) > (left.y - base.y) * (right.x - base.x);
    }

    private static boolean insideOfTriangle(Point t1, Point t2, Point t3, Point pt) {
        if (!leftTurn(t1, t2, t3)) {
            Point tmp = t2;
            t2 = t3;
            t3 = tmp;
        }
        return leftTurn(t1, t2, pt) && leftTurn(t1, pt, t3) && leftTurn(t2, t3, pt);
    }

    private static Point[] tri(int x1, int y1, int x2, int y2, int x3, int y3) {
        return tri(new Point(x1, y1), new Point(x2, y2), new Point(x3, y3));
    }

    private static Point[] tri(Point a, Point b, Point c) {
        return new Point[] { a, b, c };
    }

    private static final int MAXC = 10000;

    private static final Iterator<Point> uncorrelated = new Iterator<Point>() {
        public Point next() {
            return new Point(random.nextInt(2 * MAXC + 1) - MAXC, random.nextInt(2 * MAXC + 1) - MAXC);
        }
        public boolean hasNext() {
            return true;
        }
        public void remove() {}
    };

    private static final Iterator<Point> correlated = new Iterator<Point>() {
        public Point next() {
            int x = random.nextInt(2 * MAXC + 1) - MAXC;
            int y = x + random.nextInt(2001) - 1000;
            y = Math.min(MAXC, Math.max(-MAXC, y));
            return new Point(x, y);
        }
        public boolean hasNext() {
            return true;
        }
        public void remove() {}
    };

    private static Point[] hull(Point[] poly) {
        for (int i = 0; i < poly.length; ++i) {
            if (poly[i].x < poly[0].x || poly[i].x == poly[0].x && poly[i].y < poly[0].y) {
                Point tmp = poly[i];
                poly[i] = poly[0];
                poly[0] = tmp;
            }
        }
        final Point base = poly[0];
        for (int i = 0; i < poly.length; ++i) {
            poly[i] = poly[i].subtract(base);
        }
        Arrays.sort(poly, 1, poly.length, new Comparator<Point>() {
            public int compare(Point lhs, Point rhs) {
                int vmul = lhs.vmul(rhs);
                if (vmul == 0) {
                    int smul1 = lhs.smul(lhs);
                    int smul2 = rhs.smul(rhs);
                    return smul1 < smul2 ? -1 : smul1 == smul2 ? 0 : 1;
                } else {
                    return -vmul;
                }
            }
        });
        List<Point> stack = new ArrayList<Point>();
        stack.add(poly[0]);
        stack.add(poly[1]);
        for (int i = 2; i < poly.length; ++i) {
            int sz;
            while ((sz = stack.size()) > 1 && !leftTurn(stack.get(sz - 2), stack.get(sz - 1), poly[i])) {
                stack.remove(sz - 1);
            }
            stack.add(poly[i]);
        }
        for (int i = 0; i < stack.size(); ++i) {
            stack.set(i, base.add(stack.get(i)));
        }
        return stack.toArray(new Point[stack.size()]);
    }

    private static void genConvex(int count, Iterator<Point> rng, String enMsg, String ruMsg) {
        System.out.print("Generating test #" + (nTests + 1) + "...");
        List<Point[]> triangles = convexPartition(count, rng);
        count = triangles.size();
        write(triangles, "Convex polygon partition with " + count + " triangles with " + enMsg,
                         "Разбиение выпуклого многоугольника на " + count + " треугольников с " + ruMsg);
        System.out.println("done!");
    }

    private static boolean areAdjacent(Point[] p1, Point[] p2) {
        Set<Point> all = new HashSet<Point>();
        for (Point p : p1) {
            all.add(p);
        }
        for (Point p : p2) {
            all.add(p);
        }
        return all.size() == 4;
    }

    private static void genNonconvex(int count) {
        System.out.print("Generating test #" + (nTests + 1) + "...");
        List<Point[]> triangles = convexPartition(3 * count, uncorrelated);
        @SuppressWarnings({"unchecked"})
        List<Integer>[] adjacent = new List[triangles.size()];
        for (int i = 0; i < triangles.size(); ++i) {
            List<Integer> adj = new ArrayList<Integer>();
            for (int j = 0; j < triangles.size(); ++j) {
                if (i != j && areAdjacent(triangles.get(i), triangles.get(j))) {
                    adj.add(j);
                }
            }
            adjacent[i] = adj;
        }
        List<Integer> indices = new ArrayList<Integer>();
        boolean[] used = new boolean[triangles.size()];
        indices.add(random.nextInt(triangles.size()));
        Set<Point> usedPoints = new HashSet<Point>();
        used[indices.get(0)] = true;
        usedPoints.addAll(Arrays.asList(triangles.get(indices.get(0))));
        int frac = Math.max(1, count / 10);
        System.out.print(" [");
        while (indices.size() < count) {
            int from = indices.get(random.nextInt(indices.size()));
            int to = adjacent[from].get(random.nextInt(adjacent[from].size()));
            int oi = indices.size() / frac;
            int pointsOnTriangle = 0;
            for (Point p : triangles.get(to)) {
                if (usedPoints.contains(p)) {
                    ++pointsOnTriangle;
                }
            }
            if (pointsOnTriangle == 3) {
                int countActiveNeighbours = 0;
                for (int a : adjacent[to]) {
                    if (used[a]) {
                        ++countActiveNeighbours;
                    }
                }
                if (countActiveNeighbours == 1) {
                    continue;
                }
            }
            if (!used[to]) {
                used[to] = true;
                indices.add(to);
                usedPoints.addAll(Arrays.asList(triangles.get(to)));
            }
            int ni = indices.size() / frac;
            if (oi != ni) {
                System.out.print(".");
            }
        }
        System.out.print("]");
        List<Point[]> rv = new ArrayList<Point[]>();
        for (int i = 0; i < indices.size(); ++i) {
            rv.add(triangles.get(indices.get(i)));
        }
        write(rv, "Random nonconvex polygon with " + rv.size() + " partition triangles", 
                "Случайный невыпуклый многоугольник с " + rv.size() + " треугольниками в разбиении");
        System.out.println("done!");
    }

    private static List<Point[]> convexPartition(int count, Iterator<Point> rng) {
        Point[] random = new Point[count];
        for (int i = 0; i < count; ++i) {
            random[i] = rng.next();
        }
        Point[] hull = hull(random);
        List<Point[]> triangles = new ArrayList<Point[]>();
        for (int i = 2; i < hull.length; ++i) {
            triangles.add(tri(hull[0], hull[i - 1], hull[i]));
        }
        List<Point> pts = new ArrayList<Point>(Arrays.asList(hull));
        int remains = (count - triangles.size()) / 2;
        int frac = Math.max(1, remains / 10);
        System.out.print("[");
        while (triangles.size() + 2 <= count) {
            Point r = rng.next();
            boolean ok = true;
            for (int i = 0; ok && i < pts.size(); ++i) {
                for (int j = i + 1; ok && j < pts.size(); ++j) {
                    if (r.subtract(pts.get(i)).vmul(r.subtract(pts.get(j))) == 0) {
                        ok = false;
                        break;
                    }
                }
            }
            if (!ok) {
                continue;
            }
            for (int i = 0; i < triangles.size(); ++i) {
                Point[] triangle = triangles.get(i);
                if (insideOfTriangle(triangle[0], triangle[1], triangle[2], r)) {
                    triangles.remove(i);
                    triangles.add(tri(triangle[0], triangle[1], r));
                    triangles.add(tri(triangle[1], r, triangle[2]));
                    triangles.add(tri(r, triangle[2], triangle[0]));
                    pts.add(r);
                    break;
                }
            }
            int or = remains / frac;
            --remains;
            int nr = remains / frac;
            if (or != nr) {
                System.out.print(".");
            }
        }
        System.out.print("] ");
        return triangles;
    }

    public static void main(String[] args) {
        write(Arrays.<Point[]>asList(
            tri(-31, -176,          71, -244,           56, 41)
        ), "Test with one triangle", "Тест с одним треугольником");
        write(Arrays.asList(
            tri(-31, -176,          71, -244,           56, 41),
            tri(119, 52,            71, -244,           56, 41)
        ), "Test with two adjacent triangles", "Тест с двумя смежным треугольниками");
        write(Arrays.asList(
            tri(-10000, -10000,     10000, -10000,      -10000, 10000),
            tri(10000, -10000,      -10000, 10000,      10000, 10000)
        ), "Maximum square constructed from two triangles", "Максимальный квадрат, составленный из двух треугольников");
        write(Arrays.asList(
            tri(9999, 10000,        -10000, 9999,       0, 1),
            tri(-9999, -10000,      0, 1,               10000, -9999),
            tri(0, 1,               -10000, 9999,       -9999, -10000),
            tri(10000, -9999,       9999, 10000,        0, 1)
        ), "Almost maximum square of four triangles", "Почти максимальный квадрат из четырех треугольников");
        write(Arrays.asList(
            tri(9999, 10000,        -10000, 9999,       0, 2),
            tri(-9999, -10000,      0, 2,               10000, -9999),
            tri(0, 2,               -10000, 9999,       -9999, -10000),
            tri(10000, -9999,       9999, 10000,        0, 2),
            tri(-10000, 9999,       -9999, 10000,       9999, 10000),
            tri(10000, -9999,       9999, 10000,        10000, 9999),
            tri(-10000, -9999,      -10000, 9999,       -9999, -10000),
            tri(-9999, -10000,      9999, -10000,       10000, -9999)
        ), "Maximum square with cut corners, 8 triangles", "Максимальный квадрат с обрезанными углами, 8 треугольников");

        for (int i = 0; i < 25; ++i) {
            Iterator<Point> it = (i % 2 == 0) ? correlated : uncorrelated;
            genConvex((i + 1) * 40, it,
                    it == correlated ? "correlated point generator" : "uncorrelated point generator",
                    it == correlated ? "коррелированным генератором точек" : "некоррелированным генератором точек"
            );
        }

        for (int i = 0; i < 20; ++i) {
            genNonconvex((i + 1) * 40 + 200);
        }
    }
}
