精彩的人生

好好工作,好好生活

BlogJava 首页 新随笔 联系 聚合 管理
  147 Posts :: 0 Stories :: 250 Comments :: 0 Trackbacks

``How am I ever going to solve this problem?" said the pilot.

Indeed, the pilot was not facing an easy task. She had to drop packages at specific points scattered in a dangerous area. Furthermore, the pilot could only fly over the area once in a straight line, and she had to fly over as many points as possible. All points were given by means of integer coordinates in a two-dimensional space. The pilot wanted to know the largest number of points from the given set that all lie on one line. Can you write a program that calculates this number?

Your program has to be efficient!

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The input consists of N pairs of integers, where 1 < N < 700. Each pair of integers is separated by one blank and ended by a new-line character. The list of pairs is ended with an end-of-file character. No pair will occur twice.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
The output consists of one integer representing the largest number of points that all lie on one line.

Sample Input

1

1 1
2 2
3 3
9 10
10 11

Sample Output

3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

public class Problem270 {

    
/**
     * 
@param args
     
*/

    
public static void main(String[] args) {
        
int times=0;
        
        ArrayList param 
= new ArrayList();
        ArrayList result 
= new ArrayList();
        
        
int largestNum = 0;
        
        String s
=null;
        
try {
            
//get start point
            BufferedReader cin = new BufferedReader( new InputStreamReader( System.in ) );
            s 
= cin.readLine();
            
            
if(s==null || s.length()<1 || !isNumber(s)){
                
if(Integer.parseInt(s)>=700 || Integer.parseInt(s)<=0){
                    System.out.println(
"error! the start number must between 0 to 700");
                    
return;
                }
else{
                    System.out.println(
"input a number!!");
                }

            }

            
            times 
= Integer.parseInt(s);
            
            
//get the space line
            cin = new BufferedReader( new InputStreamReader( System.in ) );
            s 
= cin.readLine();
            
if(s.trim().length()>0){
                System.out.println(
"you must enter a space line here!!");
                
return;
            }

            
            
for(int i=0; i<times; i++){    
                
while(true){
                    cin 
= new BufferedReader( new InputStreamReader( System.in ) );
                    s 
= cin.readLine();
                    
if(s.trim().length()<1){
                        result.add(calculate(param, largestNum));
                        param 
= new ArrayList();
                        largestNum
=0;
                        
break;
                    }

                                
                    
if(isParams(s)){
                        param.add(s);
                    
                        
//set largestNum
                        String[] strs = s.split(" ");
                        
if(largestNum<Integer.parseInt(strs[0])){
                            largestNum
=Integer.parseInt(strs[0]);
                        }

                        
if(largestNum<Integer.parseInt(strs[1])){
                            largestNum
=Integer.parseInt(strs[1]);
                        }

                    }
else{
                        System.out.println(
"error param!");
                        
return;
                    }

                }

            }

            
//            //after get params, creat a new array
//            int[][] road = initRoad(param, largestNum);
//            s = (String) param.get(startpoint-1);
//            String[] strs = s.split(" ");
//            
//            int x = Integer.parseInt(strs[0]);
//            int y = Integer.parseInt(strs[1]);
//            
//            calculate(road, x, y);
            
            
for(int i=0; i<times; i++){
                System.out.println(result.get(i));
                System.out.println(
"");
            }

            
            
        }
 catch (IOException e) {
            
// TODO Auto-generated catch block
            e.printStackTrace();
        }
    

    }

    
    
private static String calculate(ArrayList param, int largestNum) {
        
int[][] road = initRoad(param, largestNum);
            
        
int tempPointNum=0;
        
        
//leftbottom
        for(int i=0; i<road.length; i++){
            
int temp = getTempPointNum(00, i, road.length-1, road);
            
if(temp>tempPointNum){
                tempPointNum 
= temp;
            }

        }

        
//        rightbottom
        for(int i=0; i<road.length; i++){
            
int temp = getTempPointNum(00, road.length-1, i, road);
            
if(temp>tempPointNum){
                tempPointNum 
= temp;
            }

        }

        
//        leftbottom
        for(int i=0; i<road.length; i++){
            
int temp = getTempPointNum(road.length-1, road.length-1, i, road.length-1, road);
            
if(temp>tempPointNum){
                tempPointNum 
= temp;
            }

        }

        
//        rightbottom
        for(int i=0; i<road.length; i++){
            
int temp = getTempPointNum(road.length-1, road.length-1, road.length-1, road.length-1, road);
            
if(temp>tempPointNum){
                tempPointNum 
= temp;
            }

        }

        
        
return tempPointNum + "";
    }


    
private static int getTempPointNum(int x1, int y1, int x2, int y2, int[][] road) {
        
int result=0;
        
if(x1==x2){
            
for(int i=y1>y2?y2:y1; i<(y1>y2?y1:y2); i++){
                
if(road[x1][i]==1)
                    result
++;
            }

            
return result;
        }

        
        
        
double liner = Math.abs(y1-y2)/Math.abs(x1-x2);
        
if(liner>=0){
            
if(x1>x2){
                
for(int i=x2; i<=x1; i++){
                    
int tempY = (int)((i-x2)*liner + y2);
                    
if(x2==i&&y2==tempY){
                        
                    }
else if((y2-tempY)/(x2-i)==liner){
                        
                    }
else{
                        
continue;
                    }

                    
                    
if(road[i][tempY]==1)
                        result
++;
                }

            }
else{
                
for(int i=x1; i<=x2; i++){
                    
int tempY = (int)((i-x1)*liner + y1);
                    
if(x1==i&&y1==tempY){
                        
                    }
else if((y1-tempY)/(x1-i)==liner){
                        
                    }
else{
                        
continue;
                    }

                    
                    
if(road[i][tempY]==1)
                        result
++;
                }

            }

        }

        
return result;
    }


    
private static int[][] initRoad(ArrayList param, int largestNum) {
        
// TODO Auto-generated method stub
        int[][] result = new int[largestNum][largestNum];
        
        String s
=null;
        String[] strs;
        
for(int i=0; i<param.size(); i++){
            s 
= (String) param.get(i);
            strs 
= s.split(" ");
            result[Integer.parseInt(strs[
0])-1][Integer.parseInt(strs[1])-1= 1;
        }
        
        
return result;
    }


    
private static boolean isParams(String s) {
        String[] strs 
= s.split(" ");
        
if(strs.length!=2){
            
return false;
        }

        
        
if(isNumber(strs[0]) && isNumber(strs[1])){
            
return true;
        }

        
        
return false;
    }


    
private static boolean isNumber(String s) {
        
boolean result = true;
        
for(int i=0; i<s.length(); i++){
            
if(s.charAt(i)>='0' && s.charAt(i)<='9'){
                
continue;
            }
else{
                result
=false;
                
break;
            }

        }

        
return result;
    }


}

posted on 2005-12-09 10:00 hopeshared 阅读(800) 评论(0)  编辑  收藏 所属分类: Google Code Jam

只有注册用户登录后才能发表评论。


网站导航: