Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2018
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.61 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.text.DecimalFormat;
  5.  
  6. public class ProblemDSurveillance2 {
  7.     static class Point {
  8.         double x,y;
  9.  
  10.         Point(double x, double y) {
  11.             this.x = x;
  12.             this.y = y;
  13.         }
  14.     }
  15.  
  16.     private static double minRadius;
  17.     private static double minOfFirst;
  18.     private static int  n;
  19.  
  20.     public static void main(String args[]) throws IOException {
  21.         InputStreamReader r = new InputStreamReader(System.in);
  22.         BufferedReader in = new BufferedReader(r);
  23.  
  24.         int t = Integer.valueOf(in.readLine());
  25.         for (int i=1; i<=t; i++) {
  26.             n = Integer.valueOf(in.readLine());
  27.             Point[] points = new Point[n];
  28.             for (int j=0; j<n; j++) {
  29.                 String parts[] = in.readLine().split(" ");
  30.                 points[j] = new Point(Double.valueOf(parts[0]), Double.valueOf(parts[1]));
  31.             }
  32.  
  33.             minDistance(points,n);
  34.             double maxArea = ternarySearch(minOfFirst - minRadius, minOfFirst, 0.0000000000001);
  35.  
  36.             DecimalFormat df = new DecimalFormat("##.########");
  37.             System.out.println("Case #" + i + ": " + df.format(f(maxArea)));
  38.             if (i!=t) in.readLine();
  39.         }
  40.     }
  41.  
  42.  
  43.     private static void minDistance(Point p[], int n) {
  44.         minRadius = Double.MAX_VALUE;
  45.         minOfFirst = Double.MAX_VALUE;
  46.         boolean isFirst=true;
  47.         for (int i = 0; i < n; i++) {
  48.             for (int j = i + 1; j < n; j++) {
  49.                 double distance = dist(p[i], p[j]);
  50.                 if (distance <= minRadius) {
  51.                     minRadius = distance;
  52.                     if (i!=0) isFirst=false;
  53.                 }
  54.             }
  55.             if (i==0) minOfFirst = minRadius;
  56.         }
  57.         if (!isFirst) minRadius = minRadius/2;
  58.     }
  59.  
  60.     private static double ternarySearch(double left, double right, double absolutePrecision) {
  61.     if(Math.abs(right - left) < absolutePrecision)
  62.         return (left + right)/2;
  63.  
  64.     double leftThird = (2*left + right)/3;
  65.     double rightThird = (left + 2*right)/3;
  66.  
  67.     if (f(leftThird) < f(rightThird))
  68.         return ternarySearch(leftThird, right, absolutePrecision);
  69.     else
  70.         return ternarySearch(left, rightThird, absolutePrecision);
  71.     }
  72.  
  73.     private static double f(double j) {
  74.         return Math.PI*j*j + (n-1)*Math.PI*(minOfFirst-j)*(minOfFirst-j);
  75.     }
  76.  
  77.  
  78.     private static double dist(Point p1, Point p2) {
  79.         return Math.sqrt(Math.pow(p1.x - p2.x,2) + Math.pow(p1.y - p2.y,2));
  80.     }
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement