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

}
}

Together, Power Plants and...

The Symbiotic Solution: Power Plants Fueling Global Greenhouses In the...

Regional Lenders Are Merging...

The Consolidation Wave: Why Regional Lenders Are Merging to...

Rush announce reunion tour...

Rush Announces Triumphant Reunion Tour Five Years After Neil...

Partnership turns soggy paddocks...

The Kidney of the Landscape: How Partnerships are Revitalizing...

More CEOs want Elon...

The High-Stakes Gamble: Why 'Moonshot' CEO Pay is Worrying...

I did not expect...

I Did Not Expect This Midrange Sony Soundbar to...

Together, Power Plants and Greenhouses Can Feed Humanity.

The Symbiotic Solution: Power Plants Fueling Global Greenhouses In the quest for sustainable practices and improved global food security, engineers are increasingly looking toward solutions...

Regional Lenders Are Merging to Answer the Challenge From Megabanks

The Consolidation Wave: Why Regional Lenders Are Merging to Fight Megabank Dominance The landscape of American banking is undergoing a rapid transformation, characterized by a...

Rush announce reunion tour five years after the death of drummer Neil Peart

Rush Announces Triumphant Reunion Tour Five Years After Neil Peart’s Passing The landscape of progressive rock was irrevocably changed five years ago with the passing...

Partnership turns soggy paddocks into wetlands – and a model for cleaner waterways

The Kidney of the Landscape: How Partnerships are Revitalizing Waterways Through Wetland Creation Wetlands have long been dubbed the 'kidneys of the landscape,' and for...

More CEOs want Elon Musk–style ‘moonshot’ pay packages—but comp experts are raising alarms

The High-Stakes Gamble: Why 'Moonshot' CEO Pay is Worrying Compensation Experts A new, highly ambitious trend is sweeping through corporate boardrooms: the demand for "moonshot"...

I did not expect this midrange Sony soundbar to rival my Sonos system like this

I Did Not Expect This Midrange Sony Soundbar to Rival My Sonos System Sony's Bravia Theater System 6, a mid-range soundbar, has surprisingly impressed reviewers...

Combination of coaching, personnel has LSU’s defense ‘playing great’

LSU's Defensive Surge: A Winning Combination of Coaching and Personnel The LSU Tigers' impressive defensive turnaround hasn't been a matter of luck; it's a strategic...

Disney’s Kimmel suspension shows Trump’s increasing grip over media

Disney’s Kimmel Suspension: Trump’s Tightening Grip on Media? The recent suspension of Jimmy Kimmel from Disney, following controversial comments about former President Trump, has sparked...

New breath sensor detects diabetes quickly and easily

New Breath Sensor Detects Diabetes Quickly and Easily Diabetes affects millions, often going undiagnosed until significant health problems arise. Traditional methods of diagnosis, such...