首页 > 专题系列 > Java解POJ > POJ 2780 Linearity [解题报告] Java
2013
11-12

POJ 2780 Linearity [解题报告] Java

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();
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		
  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