import java.util.Scanner; import java.util.ArrayList; public class pizza_bobk { private class Point { public double x,y; } private static final int N_CIRCLE = 4000, N_SLICE = N_CIRCLE + 8; private int r, dx,dy, x,y, bdyTop,bdyBottom, bdyLeft,bdyRight, nSlices, nSlicePoints,nHullPoints; private double p; private double[] sliceArea; ArrayList circlePoints, slicePoints, hullPoints; public ArrayList quickHull(ArrayList points) { ArrayList convexHull = new ArrayList(); int minPoint = -1, maxPoint = -1; double minX = Double.MAX_VALUE; double maxX = -minX; if (points.size() < 3) return convexHull; for (int i = 0; i < points.size(); i++) { if (points.get(i).x < minX) { minX = points.get(i).x; minPoint = i; } if (points.get(i).x > maxX) { maxX = points.get(i).x; maxPoint = i; } } Point A = points.get(minPoint); Point B = points.get(maxPoint); convexHull.add(A); convexHull.add(B); points.remove(A); points.remove(B); ArrayList leftSet = new ArrayList(); ArrayList rightSet = new ArrayList(); for (int i = 0; i < points.size(); i++) { Point p = points.get(i); if (pointLocation(A, B, p) == -1) leftSet.add(p); else if (pointLocation(A, B, p) == 1) rightSet.add(p); } hullSet(A, B, rightSet, convexHull); hullSet(B, A, leftSet, convexHull); return convexHull; } public double distance(Point A, Point B, Point C) { double ABx = B.x - A.x; double ABy = B.y - A.y; double num = ABx * (A.y - C.y) - ABy * (A.x - C.x); if (num < 0) num = -num; return num; } public void hullSet(Point A, Point B, ArrayList set, ArrayList hull) { int insertPosition = hull.indexOf(B); if (set.size() == 0) return; if (set.size() == 1) { Point p = set.get(0); set.remove(p); hull.add(insertPosition, p); return; } double dist = -1; int furthestPoint = -1; for (int i = 0; i < set.size(); i++) { Point p = set.get(i); double distance = distance(A, B, p); if (distance > dist) { dist = distance; furthestPoint = i; } } Point P = set.get(furthestPoint); set.remove(furthestPoint); hull.add(insertPosition, P); // Determine who's to the left of AP ArrayList leftSetAP = new ArrayList(); for (int i = 0; i < set.size(); i++) { Point M = set.get(i); if (pointLocation(A, P, M) == 1) leftSetAP.add(M); } // Determine who's to the left of PB ArrayList leftSetPB = new ArrayList(); for (int i = 0; i < set.size(); i++) { Point M = set.get(i); if (pointLocation(P, B, M) == 1) leftSetPB.add(M); } hullSet(A, P, leftSetAP, hull); hullSet(P, B, leftSetPB, hull); } public int pointLocation(Point A, Point B, Point P) { double cp1 = (B.x - A.x) * (P.y - A.y) - (B.y - A.y) * (P.x - A.x); if (cp1 > 0) return 1; else if (cp1 == 0) return 0; else return -1; } private void dumpData() { System.out.println("radius: " + r); System.out.println("slice size: " + dx + ' ' + dy); System.out.println("slice corner: " + x + ',' + y); System.out.println("threshold: " + p); System.out.println("left-right bdy: " + bdyLeft + ' ' + bdyRight); System.out.println("bottom-top bdy: " + bdyBottom + ' ' + bdyTop); System.out.println("slices: " + nSlices); } private double findArea() { double area = 0; Point x,y; if (hullPoints.size() < 3) return 0.0; y = hullPoints.get(0); for (int i=0;i(); slicePoints = new ArrayList(); for (int i=0;i 0.0 && sliceArea[i] < p * maxArea) nBad++; System.out.println(nBad); } public static void main(String[] args) { pizza_bobk solver = new pizza_bobk(); solver.solve(); } }