2013
11-12

# Linearity

Alice often examines star maps where stars are represented by points in a plane and there is a Cartesian coordinate for each star. Let the Linearity of a star map be the maximum number of stars in a straight line.

For example, look at the star map shown on the figure above, the Linearity of this map is 3, because the star 1, star 2, and star 5 are within the same straight line, and there is no straight line that passes 4 stars.

You are to write a program to find the Linearity of a star map.

Input will contain multiple test cases. Each describes a star map.

For each test case, the first line of the input contains the number of stars N (2 <= N <= 1000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0 <= X, Y <= 1000). There can be only one star at one point of the plane.

Output the Linearity of the map in a single line.

5
0 0
2 0
0 2
1 1
2 2


3

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Point implements Comparable {
double x,y;
public int compareTo(Object obj){
Point temp = (Point) obj;
if(temp.x!=this.x){
if(temp.x< this.x) return 1;
return -1;
}
if(temp.y< this.y) return 1;
return -1;
}
}
public class Main {
static final int N = 1000+10;
static int n;
static double p[] = new double[N];
static Point point[] = new Point[N];
static void start(){
for(int i=0;i< N;++i)
point[i] = new Point();
}

public static void main(String[]args) throws Exception{
int i;
start();

while(cin.nextToken()!=StreamTokenizer.TT_EOF){
n = (int) cin.nval;
for(i=0;i< n;++i){
cin.nextToken();
point[i].x = cin.nval;
cin.nextToken();
point[i].y = cin.nval;
}
if(n<=2) System.out.println(n);
else System.out.println(solve());
}
}

public static int solve(){
int i,j,k,cnt,ans=1;
Arrays.sort(point,0,n);
for(i=0;i< n;++i){
for(k=0,j=i+1;j< n;++j){
if(point[i].x==point[j].x)
p[k++] = 10000000000.0;
else
p[k++] = (point[j].y-point[i].y)/(point[j].x-point[i].x);
}
Arrays.sort(p,0,k);
cnt = 1;
//for(j=0;j< k;++j) System.out.print(p[j]+" ");System.out.println();
for(j=1;j< k;++j){
if(p[j]==p[j-1])
++cnt;
else{
ans = cnt>ans?cnt:ans;
cnt = 1;
}
}
ans = cnt>ans?cnt:ans;
}
return ans+1;
}
}

1. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

2. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false