# 精彩的人生

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.

```1

1 1
2 2
3 3
9 10
10 11```

## Sample Output

`3import 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(0, 0, i, road.length-1, road);            if(temp>tempPointNum){                tempPointNum = temp;            }        }        //        rightbottom        for(int i=0; i<road.length; i++){            int temp = getTempPointNum(0, 0, 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 阅读(851) 评论(0)  编辑  收藏 所属分类: Google Code Jam

 只有注册用户登录后才能发表评论。 网站导航: 相关文章: