hdu 5112 A Curious Matt （java，快速输入）

A Curious Matt

Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 512000/512000 K (Java/Others)
Total Submission(s): 2397    Accepted Submission(s): 1355

Problem Description

There is a curious man called Matt.

One day, Matt's best friend Ted is wandering on the non-negative half of the number line. Matt finds it interesting to know the maximal speed Ted may reach. In order to do so, Matt takes records of Ted’s position. Now Matt has a great deal of records. Please help him to find out the maximal speed Ted may reach, assuming Ted moves with a constant speed between two consecutive records.

 

Input

The first line contains only one integer T, which indicates the number of test cases.

For each test case, the first line contains an integer N (2 ≤ N ≤ 10000),indicating the number of records.

Each of the following N lines contains two integers t _i and x _i (0 ≤ t _i, x _i ≤ 10 ⁶), indicating the time when this record is taken and Ted’s corresponding position. Note that records may be unsorted by time. It’s guaranteed that all t _i would be distinct.

 

Output

For each test case, output a single line “Case #x: y”, where x is the case number (starting from 1), and y is the maximal speed Ted may reach. The result should be rounded to two decimal places.

 

Sample Input

   
   2
3
2 2
1 1
3 4
3
0 3
1 5
2 0
  
  

 

Sample Output

  
  Case #1: 2.00
Case #2: 5.00


  
  

   
   

    
    Hint
   
   
In the first sample, Ted moves from 2 to 4 in 1 time unit. The speed 2/1 is maximal.
In the second sample, Ted moves from 5 to 0 in 1 time unit. The speed 5/1 is maximal. 
  
  
 
 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5112

解题思路：给定n个时间点的坐标和n个时间点对应的横坐标，求整段时间里的最大速度。这题解题思路很简单，就对时间按从小到大排一下顺序，然后计算相邻时间点里速度，取最大速度即可。但这题用java实现有几点要注意：

       1、C++里建结构体直接用struct就行，Java是定义成一个类的形式，在主函数里申请空间时用多少申请多少，比如<类名>[] <对象名> = new<类名>[n] ;不能多申请，和C++的排序函数不同，C++传入排序长度，Java不传，多余的空间会跟着排序。输入结构体里的变量时要边申请空间边输入。

       2、重写Comparator要写在主函数里面，格式为：

       Comparator <类名> cmp = new Comparator<类名>(){
                @Override
                public int compare(类名 o1, 类名 o2){

                }

           排序函数 ：Arrays.sort(<数组名>,cmp);

       3、 确定小数点后几位，比如保留ans的小数点后两位：new DecimalFormat("0.00").format(ans)

       4、io快速读入，这题不用这个方法大概是2s+，会超时，用快速读入后就在1s内了。原理是：Scanner读入是字符读入，要换成字符流读入会更快。但是io读入要重写方法，有些复杂，多理解记忆一下。 定义myScanner类：重写读入string、int 、double等方法（详见代码）。

代码如下：

import java.util.*;
import java.text.*;
import java.io.*;

public class Main {
	static class Recordes{
		double t,x;  
	}
	
	public static int T, n;
	
	static class myScanner {   //写输入类
		
		BufferedReader br;
		StringTokenizer st;
		
		public myScanner(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
			st = new StringTokenizer("");
		}
		
		public String nextLine() {
			try {              //此处要捕获异常
				return br.readLine();
			} catch (IOException e){
				return null;
			}
		}
		
		public boolean hasNext() {
			while(!st.hasMoreTokens()) {
				String s = nextLine();
				if (s == null) {
					return false;
				}
				st = new StringTokenizer(s);
			}
			return true;
		}
		
		public String next() {
			hasNext();
			return st.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		
	}
	
    public static void main(String[] args) {
       myScanner sc = new myScanner(System.in);
       PrintWriter pw = new PrintWriter(System.out); 
       T = sc.nextInt();
       for(int ca = 1;ca<=T;ca++){
    	   n = sc.nextInt();
    	   Recordes[] re = new Recordes[n];
    	   for(int i=0;i<n;i++){
    		   re[i] = new Recordes();
    		   re[i].t = sc.nextDouble();
    		   re[i].x = sc.nextDouble();
    		   
    	   }
    	   Comparator <Recordes> cmp = new Comparator<Recordes>(){
    			@Override
    			public int compare(Recordes o1, Recordes o2) {
    				// TODO Auto-generated method stub
    				if( o1.t > o2.t ){
    					return 1;
    				}else if( o1.t < o2.t ){
    					return -1;
    				}else{
    					if(o1.x > o2.x){
    						return 1;
    					}else if(o1.x < o2.x){
    						return -1;
    					}else{
    						return 0;
    					}
    				}
    			}
    		};
    	   Arrays.sort(re,cmp);

    	   double ans = 0.0;
    	   for(int i=1;i<n;i++){
    		   double xx = Math.abs(re[i].x-re[i-1].x) ;
    		   double tt = re[i].t - re[i-1].t;

    		   if(tt==0){
    			   continue;
    		   }
    		   double cur = xx/tt;
    		   ans=Math.max(ans, cur);
    	   }
    	   pw.println("Case #"+ca+": "+new DecimalFormat("0.00").format(ans));
    	   pw.flush();
       }     	
    }	  
}