import javax.imageio.ImageIO;
import java.awt.*;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.*;
import java.util.List;


public class Farey extends Tests {

    public static final double COS_THRESHOLD = 0.99;

    class Ratio {
        int nom, den, gcd;

        Ratio(int nom, int den) {
            int gcd = gcd(nom, den);
            this.nom = nom;
            this.den = den;
        }

        @Override
        public String toString() {
            return nom + "/" + den;
        }
    }

    private int gcd(int a, int b) {
        if (a == 0) {
            return Math.abs(b);
        } else {
            return gcd(b % a, a);
        }
    }

//    void run() {
//        int n = 1000_000;
//        int maxC = 1000_000_000;
//
//        List<Point> points = genRandomVectors(n, maxC);
//        drawTest(points);
////        List<GGPoint> points = genFarey(n);
//        System.out.println(points.size());
//        for (Point p : points) {
//            System.out.println(p.x + " " + p.y);
//        }
//    }

    Random random = new Random(342852305892367L);
    int randomInt(int from, int to) {
        return random.nextInt(to - from) + from;
    }

    class Vector {
        final int x, y, gcd;

        Vector(int x, int y) {
            assert x != 0 && y != 0;
            this.x = x;
            this.y = y;
            gcd = Math.abs(gcd(x, y));
        }


        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Vector that = (Vector) o;
            return this.x / this.gcd == that.x / that.gcd && this.y / this.gcd == that.y / that.y;

        }

        double length() {
            return Math.hypot(x, y);
        }

        double cos(Vector that) {
            return (this.x * (double) that.x + this.y * (double) that.y) / this.length() / that.length();
        }

        @Override
        public int hashCode() {
            return 31 * (x / gcd) + (y / gcd);
        }
    }


    //                   (maxYX, maxC)
//  (-maxC, minXY)                  (maxC, maxXY)
//                   (minYX, -maxC)
    private void drawTest(List<Point> points) {
        int size = 1000;
        int border = 5;
        new File("images").mkdirs();
        long minx = points.get(0).x;
        long miny = points.get(0).y;
        long maxx = points.get(0).x;
        long maxy = points.get(0).y;
        for (Point point : points) {
            minx = Math.min(minx, point.x);
            miny = Math.min(miny, point.y);
            maxx = Math.max(maxx, point.x);
            maxy = Math.max(maxy, point.y);
        }
        long midx = (maxx + minx) / 2;
        long midy = (maxy + miny) / 2;
//        midx = 0;
//        fmidy = 0;
        double scale = (size - 2 * border) / (double) Math.max(maxx - minx, maxy - miny);
        BufferedImage img = new BufferedImage(size, size, BufferedImage.TYPE_INT_RGB);
        Graphics2D g = (Graphics2D) img.getGraphics();
        g.setBackground(Color.BLACK);
        g.clearRect(0, 0, size, size);

        g.setColor(Color.YELLOW.darker().darker());
        for (Point point : points) {
            int y = (int) (-(point.y - midy) * scale + size / 2);
            int x = (int) ((point.x - midx) * scale + size / 2);
            g.drawLine(0, y, size, y);
            g.drawLine(x, 0, x, size);
        }

        g.setColor(Color.WHITE);
        for (int i = 0; i < points.size(); i++) {
            Point p0 = points.get(i);
            Point p1 = points.get((i + 1) % points.size());
            int x = p0.x;
            g.drawLine(
                    (int) ((x - midx) * scale) + size / 2,
                    (int) (-(p0.y - midy) * scale) + size / 2,
                    (int) ((p1.x - midx) * scale) + size / 2,
                    (int) (-(p1.y - midy) * scale) + size / 2
            );
        }
        g.fillOval((int) (-midx * scale + size / 2) - 3, (int) (-midy * scale + size / 2) - 3, 7, 7);
        try {
            ImageIO.write(img, "png", new File("images/farey.png"));
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }


    public static void main(String[] args) {
//        new Farey().run();
    }
}
