Binary Search - Problem: Glyph Recognition - Competitive Programming

Binary Search - Problem: Glyph Recognition

In this task you will have to solve problem G from NWERC 2017. Read the problem statement below.

Since the goal of this task is not to teach you geometry, you can use the following class that represents a regular polygon with \(n\) vertices and radius \(r\).

static double eps = 1e-8;

static class RegularPolygon {

    Point[] vertices;
    int n;
    double r;

    // create a regular polygon with n vertices and radius r
    public RegularPolygon(int n, double r) {
        this.n = n;
        this.r = r;
        vertices = new Point[n];
        double alpha = 2 * Math.PI / n;
        double cur = 0;
        for(int i = 0; i < n; i++) {
            double x = r * Math.cos(cur);
            double y = r * Math.sin(cur);
            vertices[i] = new Point(x, y);
            cur += alpha;
        }
    }

    // compute the area of the regular polygon
    public double area() {
        return 0.5 * n * r * r * Math.sin(2.0 * Math.PI / n);
    }

    // check whether the polygon contains point p
    public boolean contains(Point p) {
        int target = orient(vertices[0], vertices[1], vertices[2]);
        for(int i = 0; i < n; i++) {
            int j = (i + 1) % n;
            int o = orient(p, vertices[i], vertices[j]);
            if(o != 0 && o != target) return false;
        }
        return true;
    }

    // compute the orientation of 3 points
    private int orient(Point p, Point q, Point r) {
        double value = q.x * r.y - r.x * q.y - p.x * (r.y - q.y) + p.y * (r.x - q.x);
        return sgn(value);
    }

    // compute the sign of a double
    private int sgn(double x) {
        if(x < -eps) return -1;
        if(x > eps) return 1;
        return 0;
    }

}

Points are represented by a simple class with the two coordinates.

static class Point {

    double x, y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

}

Paste this command into your terminal:

The password to connect is

Glyph Recognition

Adapted from problem G from NWERC 2017

You are an archaeologist working at an excavation site where your team has found hundreds of clay tablets containing glyphs written in some ancient language. Not much is known about the language yet, but you know that there are only six different glyphs, each of them in the shape of a regular polygon with one vertex pointing to the right (see the figure (a) below). Only the boundary of each polygon is carved out of the clay.

You want to start analysing the language right away, so you need to get the text on the tablets into some machine readable format. Ideally, you would like to use an OCR (optical character recognition) tool for that, but you do not have one installed on your laptop and there is no internet connection at the site.

Because of this you have devised your own scheme to digitise the ancient writings: for every glyph on a tablet you first find a number of sample points that are in the carved out region, i.e. on the boundary of the polygon. Based on those sample points you then calculate a score for each of the six glyphs and mark the one with the highest score as the recognised glyph.

For a given number of corners \(k \ (3 \leq k \leq 8)\), the score is computed as follows. Two regular \(k\)-gons are fitted to the sample points, one from the inside and one from the outside, such that the following hold:

Each polygon is centered at the origin, i.e. all vertices have equal distance to \((0, 0)\).
Each polygon has a vertex on the positive x-axis.
The inner polygon is the largest such polygon containing none of the sample points.
The outer polygon is the smallest such polygon containing all of the sample points.

An example can be seen in figure (c). The score for this value of \(k\) is \(A_{inner} \ / \ A_{outer}\), where \(A_{inner}\) and \(A_{outer}\) are the areas of the inner and outer polygon, respectively.

Given a set of sample points, find the glyph with the highest score.

Input

One line with one integer \(n\), the number of sample points.
\(n\) lines, each with two integers \(x, y\), specifying a point at coordinates \((x, y)\).

No sample point is at the origin and all points are distinct.

Output

Output the optimal number of corners \(k \ (3 \leq k \leq 8)\), followed by the score obtained for that value of \(k\). Your answer will be accepted if the absolute error does not exceed \(10^{-6}\) . If several values of \(k\) result in a score that is within \(10^{-6}\) of the optimal score, any one of them will be accepted.

Constraints