Sponsors

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

}
}

Advertisement

spot_img

Celebrating Black History Month:...

As February unfolds, so does the annual celebration of...

The Path to Self-Mastery:...

Embarking on a journey of self-mastery and breaking free...

Wizards of Waverly Place...

In a spellbinding announcement, Disney has officially revealed that...

Jim Irsay’s Reported ‘Suspected...

In a shocking turn of events last month, Jim...

Coachella 2024: Iconic headliners,...

Coachella Valley Music and Arts Festival, one of the...

2024 Taiwan Election: Pivotal...

As Taiwan gears up for its 2024 presidential election,...

Celebrating Black History Month: Past, Future

As February unfolds, so does the annual celebration of Black History Month, a time to reflect on the profound contributions, resilience, and rich cultural...

The Path to Self-Mastery: Lessons from Book ‘The Mountain Is You’

Embarking on a journey of self-mastery and breaking free from self-sabotage is a transformative process that requires dedication and conscious effort. Brianna Wiest's insightful...

Wizards of Waverly Place Cast Reunites for Enchanting Revival

In a spellbinding announcement, Disney has officially revealed that the beloved fantasy series "Wizards of Waverly Place" is set for a magical comeback, featuring...

Jim Irsay’s Reported ‘Suspected Overdose’: A Closer Look

In a shocking turn of events last month, Jim Irsay, the owner of the Indianapolis Colts, was reportedly found unresponsive at his home in...

Coachella 2024: Iconic headliners, unforgettable musical experience!

Coachella Valley Music and Arts Festival, one of the most iconic and eagerly anticipated music festivals globally, has just dropped its highly anticipated lineup...

2024 Taiwan Election: Pivotal Moment in Political Landscape

As Taiwan gears up for its 2024 presidential election, the political landscape is buzzing with anticipation and fervor. With the island nation situated at...

Michael Strahan’s Daughter’s Medulloblastoma Diagnosis

In a recent and heartbreaking revelation, Michael Strahan, former NFL star and television personality, shared the devastating news of his daughter Isabella's diagnosis with...

Michigan vs. Washington: The 2024 National Championship Clash

In a highly anticipated matchup, the 2024 National Championship will witness a clash of football titans as the Michigan Wolverines square off against the...

Jason Kelce: Unmasking the Unconventional NFL Icon

In the world of professional football, where conformity often takes center stage, one player stands out as a beacon of individuality, both on and...