Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.text.DecimalFormat;
- public class ProblemDSurveillance2 {
- static class Point {
- double x,y;
- Point(double x, double y) {
- this.x = x;
- this.y = y;
- }
- }
- private static double minRadius;
- private static double minOfFirst;
- private static int n;
- public static void main(String args[]) throws IOException {
- InputStreamReader r = new InputStreamReader(System.in);
- BufferedReader in = new BufferedReader(r);
- int t = Integer.valueOf(in.readLine());
- for (int i=1; i<=t; i++) {
- n = Integer.valueOf(in.readLine());
- Point[] points = new Point[n];
- for (int j=0; j<n; j++) {
- String parts[] = in.readLine().split(" ");
- points[j] = new Point(Double.valueOf(parts[0]), Double.valueOf(parts[1]));
- }
- minDistance(points,n);
- double maxArea = ternarySearch(minOfFirst - minRadius, minOfFirst, 0.0000000000001);
- DecimalFormat df = new DecimalFormat("##.########");
- System.out.println("Case #" + i + ": " + df.format(f(maxArea)));
- if (i!=t) in.readLine();
- }
- }
- private static void minDistance(Point p[], int n) {
- minRadius = Double.MAX_VALUE;
- minOfFirst = Double.MAX_VALUE;
- boolean isFirst=true;
- for (int i = 0; i < n; i++) {
- for (int j = i + 1; j < n; j++) {
- double distance = dist(p[i], p[j]);
- if (distance <= minRadius) {
- minRadius = distance;
- if (i!=0) isFirst=false;
- }
- }
- if (i==0) minOfFirst = minRadius;
- }
- if (!isFirst) minRadius = minRadius/2;
- }
- private static double ternarySearch(double left, double right, double absolutePrecision) {
- if(Math.abs(right - left) < absolutePrecision)
- return (left + right)/2;
- double leftThird = (2*left + right)/3;
- double rightThird = (left + 2*right)/3;
- if (f(leftThird) < f(rightThird))
- return ternarySearch(leftThird, right, absolutePrecision);
- else
- return ternarySearch(left, rightThird, absolutePrecision);
- }
- private static double f(double j) {
- return Math.PI*j*j + (n-1)*Math.PI*(minOfFirst-j)*(minOfFirst-j);
- }
- private static double dist(Point p1, Point p2) {
- return Math.sqrt(Math.pow(p1.x - p2.x,2) + Math.pow(p1.y - p2.y,2));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement