TopCoder Member SRM 503 Div1 Medium KingdomXCitiesandVillages

■KingdomXCitiesandVillages

問題・解説は，Match Editorial Archiveを参考に．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5. public class KingdomXCitiesandVillages {  
6.  int INF=1<<28;  
7.  double EPS=1e-9;  
8.   
9.  int m, n;  
10.   
11.  public double determineLength(int[] cx, int[] cy, int[] vx, int[] vy) {  
12.   m=cx.length;  
13.   n=vx.length;  
14.   double sum=0;  
15.   for(int j=0;j<n;j++){  
16.    LinkedList<R> list=new LinkedList<R>();  
17.    for(int i=0;i<n;i++){  
18.     if(i!=j){  
19.      list.add(new R(Math.hypot(vx[j]-vx[i], vy[j]-vy[i]), false));  
20.     }  
21.    }  
22.    for(int i=0;i<m;i++){  
23.     list.add(new R(Math.hypot(vx[j]-cx[i], vy[j]-cy[i]), true));  
24.    }  
25.    R[] rs=list.toArray(new R[0]);  
26.    Arrays.sort(rs);  
27.    for(int i=0;i<rs.length;i++){  
28.     if(rs[i].isCity){  
29.      sum+=rs[i].d/(i+1);  
30.      break;  
31.     }else{  
32.      sum+=rs[i].d/(i+1)/(i+2);  
33.     }  
34.    }  
35.   }  
36.   return sum;  
37.  }  
38.   
39.  class R implements Comparable<R>{  
40.   double d;  
41.   boolean isCity;  
42.   R(double d, boolean isCity){  
43.    this.d=d;  
44.    this.isCity=isCity;  
45.   }  
46.   public int compareTo(R r){  
47.    if(d-r.d+EPS<0){  
48.     return -1;  
49.    }else if(d-r.d>0+EPS){  
50.     return 1;  
51.    }else{  
52.     return 0;  
53.    }  
54.   }  
55.  }  
56. }  
57.   
58.   
59. // Powered by FileEdit  
60. // Powered by TZTester 1.01 [25-Feb-2003]  
61. // Powered by CodeProcessor  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
public class KingdomXCitiesandVillages {
 int INF=1<<28;
 double EPS=1e-9;

 int m, n;

 public double determineLength(int[] cx, int[] cy, int[] vx, int[] vy) {
  m=cx.length;
  n=vx.length;
  double sum=0;
  for(int j=0;j<n;j++){
   LinkedList<R> list=new LinkedList<R>();
   for(int i=0;i<n;i++){
    if(i!=j){
     list.add(new R(Math.hypot(vx[j]-vx[i], vy[j]-vy[i]), false));
    }
   }
   for(int i=0;i<m;i++){
    list.add(new R(Math.hypot(vx[j]-cx[i], vy[j]-cy[i]), true));
   }
   R[] rs=list.toArray(new R[0]);
   Arrays.sort(rs);
   for(int i=0;i<rs.length;i++){
    if(rs[i].isCity){
     sum+=rs[i].d/(i+1);
     break;
    }else{
     sum+=rs[i].d/(i+1)/(i+2);
    }
   }
  }
  return sum;
 }

 class R implements Comparable<R>{
  double d;
  boolean isCity;
  R(double d, boolean isCity){
   this.d=d;
   this.isCity=isCity;
  }
  public int compareTo(R r){
   if(d-r.d+EPS<0){
    return -1;
   }else if(d-r.d>0+EPS){
    return 1;
   }else{
    return 0;
   }
  }
 }
}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor