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; } }