``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!
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.
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
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(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;
}
}