算法共线java

 

问题描述

　　给定2维平面上n个整点的坐标，一条直线最多能过几个点？

输入格式

　　第一行一个整数n表示点的个数
　　以下n行，每行2个整数分别表示每个点的x,y坐标。

输出格式

　　输出一个整数表示答案。

样例输入

5
0 0
1 1
2 2
0 3
2 3

样例输出

3

数据规模和约定

　　n<=1500，数据保证不会存在2个相同的点。
　　点坐标在int范围内

import java.util.Scanner;
 

 
public class ALGO_967共线 {
    //创建一个点类
    static class Point {
        int x;
        int y;
 
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Point[] points = new Point[n];
 
        for (int i = 0; i < n; i++) {
            points[i] = new Point(sc.nextInt(), sc.nextInt());
        }
 
        if (n < 3) {
            System.out.println(n);
            return;
        }
 
        int res = 0;
        for (int i = 1; i < points.length; i++) {
            int a = points[i].x, b = points[i].y;
            int xx = a - points[i - 1].x, yy = b - points[i - 1].y;
 
            int count = 0;
            for (int j = 0; j < points.length; j++) {
                if ((points[j].x - a) * yy == (points[j].y - b) * xx) {
                    count++;
                }
            }
            res = Math.max(res, count);
        }
        System.out.println(res);
    }
 
}