首页 > 专题系列 > Java解POJ > POJ 1328 Radar Installation [解题报告] Java
2013
11-09

POJ 1328 Radar Installation [解题报告] Java

Radar Installation

问题描述 :

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.

We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.



Figure A Sample Input of Radar Installations

输入:

The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.

The input is terminated by a line containing pair of zeros

输出:

For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. “-1″ installation means no solution for that case.

样例输入:

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

样例输出:

Case 1: 2
Case 2: 1

解题代码:

import java.io.PrintWriter;  

 import java.util.Arrays;  
 import java.util.Scanner;  
 /**  
  *  
  * @author 灏�  
  *  
  * 2010-6-12 涓��01:48:35  
  */ 
 public class Main {  
  static class Range implements Comparable{  
   double left,right;  
   public Range(double left,double right){  
    this.left = left;  

   this.right = right;  
   }  
   @Override 

   public int compareTo(Range range) {  
    if(range.left == left){  
     return ((Double)right).compareTo((Double)(range.right));  
    }else{  
    return ((Double)left).compareTo((Double)(range.left));  
    }  
   }  

   @Override 
   public String toString() {  
    return "(" + left + "," + right + ")";  
   }  
  }  

     
  public static void main(String[] args) {  
   Scanner scn = new Scanner(System.in);    
   
   PrintWriter out = new PrintWriter(System.out);  
   int n ,d,x,y,num;  
   double dx;  
   Range[] ranges;  
   int index = 0;  
   while(true){  
    num = 0;  
    n = scn.nextInt();  
    d = scn.nextInt();  
    if(n == 0){  
     break;  
    }  
    ranges = new Range[n];  
    for(int i = 0; i < n; i++){  
     x = scn.nextInt();  
     y = scn.nextInt();  
     if(y > d){  
      num = -1;  
     }  
     dx = Math.sqrt(d*d - y*y);  
     ranges[i] = new Range(x - dx, x + dx);  
    }  
    Arrays.sort(ranges);//���  
    if(num != -1){  
     num = calute(ranges);  
    }  
    out.format("Case %d: %d\n",++index,num);  
   }  
   out.flush();  
      
  }  
    
  private static int calute(Range[] ranges) {  
   int num = 1;  
   int n = ranges.length;  
   Range preRange = ranges[0],range;  
   for(int i = 1; i < n; i++){  
    range = ranges[i];  
    //姹���翠氦�� 
    if(range.left >= preRange.left && range.left <= preRange.right){  
     preRange.left = range.left;  
     if(range.right < preRange.right){  
      preRange.right = range.right;  
     }  
    }else{  
     num++;  
     preRange = range;  
    }  
   }  
   return num;  
  }  
}

  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  3. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.