Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2), problem: (G) Cut the pie Solution In JAVA

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
FastScanner in = new FastScanner(inputStream);
PrintWriter out = new PrintWriter(outputStream);
TaskG solver = new TaskG();
solver.solve(1, in, out);
out.close();
}

static class TaskG {
int n;
Point[] p;
Point cutPoint;
double totalArea;
double[] partial;
final double eps = 1e-10;
boolean earlyExit;

public void solve(int testNumber, FastScanner in, PrintWriter out) {
n = in.nextInt();
int numQueries = in.nextInt();
p = new Point[n];
for (int i = n – 1; i >= 0; i–) {
p[i] = new Point();
p[i].x = in.nextInt();
p[i].y = in.nextInt();
}
calcPartialAreas();
cutPoint = new Point();

for (int query = 0; query < numQueries; query++) {
double l = 0;
double r = Math.PI;
cutPoint.x = in.nextInt();
cutPoint.y = in.nextInt();
int cut0 = cut(0);
if (cut0 == 0) {
out.println(0);
continue;
}

earlyExit = false;
for (int it = 0; it < 50; it++) {
double m = 0.5 * (l + r);
if (cut(m) == cut0) {
l = m;
} else {
r = m;
}
if (earlyExit) {
l = m;
r = m;
break;
}
}
out.printf(“%.15f\n”, 0.5 * (l + r));
}
}

private void calcPartialAreas() {
partial = new double[n];
for (int i = 0; i < n; i++) {
partial[i] = cross(p[i], p[(i + 1) % n]);
if (i > 0) {
partial[i] += partial[i – 1];
}
}
totalArea = Math.abs(partial[n – 1]);
}

private int cut(double alpha) {
double a = -Math.sin(alpha);
double b = Math.cos(alpha);
double c = -a * cutPoint.x – b * cutPoint.y;
Line L = new Line(a, b, c);

int[] ex = findExtremalPoints(L);
int i = ex[0];
int j = ex[1];
if (!(side(p[i], L) >= 0 && side(p[j], L) <= 0)) {
throw new AssertionError();
}

int l = 0;
int r = (j – i + n) % n;
while (r – l > 1) {
int m = (l + r) / 2;
int k = (i + m) % n;
int s = side(p[k], L);
if (s >= 0) {
l = m;
} else {
r = m;
}
}
int u = (i + l) % n;

l = 0;
r = (i – j + n) % n;
while (r – l > 1) {
int m = (l + r) / 2;
int k = (j + m) % n;
int s = side(p[k], L);
if (s <= 0) {
l = m;
} else {
r = m;
}
}
int v = (j + l) % n;

double area = calcSignedAreaBetween(v, u);
area = Math.abs(area + cross(p[u], p[v]));
Point u1 = intersect(L, new Line(p[u], p[(u + 1) % n]));
Point v1 = intersect(L, new Line(p[v], p[(v + 1) % n]));
Point inter = intersect(new Line(p[u], p[v]), L);

if (inter != null) {
area += triangleArea(p[u], u1, inter);
area -= triangleArea(p[v], v1, inter);
}

double otherArea = totalArea – area;
checkEarlyExit(area, otherArea);
return Double.compare(area, otherArea);
}

private void checkEarlyExit(double a, double b) {
if (Math.abs(a – b) / (a + b) < 1e-4) {
earlyExit = true;
}
}

private int[] findExtremalPoints(Line L) {
double v0 = eval(L, p[0]);
double v1 = eval(L, p[1]);
boolean flip = false;
if (v0 > v1) {
flip = true;
L.flip();
v0 = -v0;
v1 = -v1;
}

int l = 0;
int r = n – 1;
while (r – l > 1) {
int m = (l + r) / 2;
double v3 = eval(L, p[m]);
double v4 = eval(L, p[(m + 1) % n]);
if (v4 >= v3 && v3 >= 0.5 * (v0 + v1)) {
l = m;
} else {
r = m;
}
}
int max = (l + 1) % n;

l = 0;
r = n – 1;
while (r – l > 1) {
int m = (l + r) / 2;
double v3 = eval(L, p[(max + m) % n]);
double v4 = eval(L, p[(max + m + 1) % n]);
if (v4 < v3) {
l = m;
} else {
r = m;
}
}
int min = (max + l + 1) % n;

if (flip) {
L.flip();
return new int[]{min, max};
}
return new int[]{max, min};
}

private double calcSignedAreaBetween(int a, int b) {
double res = 0;
if (a <= b) {
res = partial[b – 1];
if (a > 0) {
res -= partial[a – 1];
}
} else {
res = partial[n – 1];
if (a > 0) {
res -= partial[a – 1];
}
if (b > 0) {
res += partial[b – 1];
}
}
return res;
}

private double eval(Line l, Point p) {
double s = l.a * p.x + l.b * p.y + l.c;
return s;
}

private int side(Point p, Line l) {
double s = l.a * p.x + l.b * p.y + l.c;
if (Math.abs(s) < eps) {
return 0;
}
return s < 0 ? -1 : 1;
}

private Point intersect(Line l1, Line l2) {
double det = l1.a * l2.b – l1.b * l2.a;
if (Math.abs(det) < eps) {
return null;
}
Point res = new Point();
res.x = -(l1.c * l2.b – l1.b * l2.c) / det;
res.y = -(l1.a * l2.c – l1.c * l2.a) / det;
return res;
}

private double triangleArea(Point p1, Point p2, Point p3) {
double x1 = p1.x – p3.x;
double y1 = p1.y – p3.y;
double x2 = p2.x – p3.x;
double y2 = p2.y – p3.y;
return Math.abs(x1 * y2 – x2 * y1);
}

double cross(Point a, Point b) {
return a.x * b.y – a.y * b.x;
}

class Point {
double x;
double y;

}

class Line {
double a;
double b;
double c;

Line(double a, double b, double c) {
this.a = a;
this.b = b;
this.c = c;
}

Line(Point p1, Point p2) {
a = p1.y – p2.y;
b = p2.x – p1.x;
c = -p1.x * a – p1.y * b;
}

void flip() {
a = -a;
b = -b;
c = -c;
}

}

static class FastScanner {
private BufferedReader in;
private StringTokenizer st;

public FastScanner(InputStream stream) {
in = new BufferedReader(new InputStreamReader(stream));
}

public String next() {
while (st == null || !st.hasMoreTokens()) {
try {
String rl = in.readLine();
if (rl == null) {
return null;
}
st = new StringTokenizer(rl);
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return st.nextToken();
}

public int nextInt() {
return Integer.parseInt(next());
}

}
}

Related Reading: Explore our comprehensive guide on Google Trends & technology research strategies.