题解 | 直线上的点

#include <bits/stdc++.h>
using namespace std;

// 三维点结构
struct Point {
    int x, y, z;
    Point(int _x = 0, int _y = 0, int _z = 0) : x(_x), y(_y), z(_z) {}
    
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y && z == other.z;
    }
};

// 直线特征结构
struct LineFeature {
    double dx, dy;  // 相对于z的斜率
    bool isParallelZ;  // 是否平行于z轴
    
    bool operator==(const LineFeature& other) const {
        if (isParallelZ != other.isParallelZ) return false;
        if (isParallelZ) return true;
        return abs(dx - other.dx) < 1e-10 && abs(dy - other.dy) < 1e-10;
    }
};

// 哈希函数
struct LineFeatureHash {
    size_t operator()(const LineFeature& f) const {
        if (f.isParallelZ) return 0;
        return hash<double>()(f.dx) ^ hash<double>()(f.dy);
    }
};

class Solution {
public:
    int findMaxPoints(vector<Point>& points) {
        int n = points.size();
        if (n <= 2) return n;
        
        int maxPoints = 0;
        
        // 遍历每个基准点
        for (int i = 0; i < n; i++) {
            unordered_map<LineFeature, int, LineFeatureHash> slopeCount;
            int duplicates = 1;  // 包含基准点自身
            
            // 遍历其他点
            for (int j = i + 1; j < n; j++) {
                if (points[i] == points[j]) {
                    duplicates++;
                    continue;
                }
                
                // 计算直线特征
                LineFeature feature = getLineFeature(points[i], points[j]);
                slopeCount[feature]++;
            }
            
            // 找出当前基准点的最大共线点数
            int localMax = duplicates;
            for (const auto& pair : slopeCount) {
                localMax = max(localMax, pair.second + duplicates);
            }
            
            maxPoints = max(maxPoints, localMax);
        }
        
        return maxPoints;
    }
    
private:
    LineFeature getLineFeature(const Point& p1, const Point& p2) {
        LineFeature feature;
        int dz = p2.z - p1.z;
        
        if (dz == 0) {
            feature.isParallelZ = true;
            feature.dx = feature.dy = 0;
        } else {
            feature.isParallelZ = false;
            feature.dx = (double)(p2.x - p1.x) / dz;
            feature.dy = (double)(p2.y - p1.y) / dz;
        }
        
        return feature;
    }
};

int main() {
    int n;
    cin >> n;
    
    vector<Point> points;
    for (int i = 0; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        points.emplace_back(x, y, z);
    }
    
    Solution solution;
    cout << solution.findMaxPoints(points) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    // 三维点结构
    static class Point {
        int x, y, z;

        Point(int _x, int _y, int _z) {
            this.x = _x;
            this.y = _y;
            this.z = _z;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (!(obj instanceof Point)) return false;
            Point other = (Point) obj;
            return x == other.x && y == other.y && z == other.z;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y, z);
        }
    }

    // 直线特征结构
    static class LineFeature {
        double dx, dy;  // 相对于z的斜率
        boolean isParallelZ;  // 是否平行于z轴

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (!(obj instanceof LineFeature)) return false;
            LineFeature other = (LineFeature) obj;
            if (isParallelZ != other.isParallelZ) return false;
            if (isParallelZ) return true;
            return Math.abs(dx - other.dx) < 1e-10 && Math.abs(dy - other.dy) < 1e-10;
        }

        @Override
        public int hashCode() {
            if (isParallelZ) return 0;
            return Objects.hash(dx, dy);
        }
    }

    static class Solution {
        public int findMaxPoints(Point[] points) {
            int n = points.length;
            if (n <= 2) return n;

            int maxPoints = 0;

            // 遍历每个基准点
            for (int i = 0; i < n; i++) {
                Map<LineFeature, Integer> slopeCount = new HashMap<>();
                int duplicates = 1;  // 包含基准点自身

                // 遍历其他点
                for (int j = 0; j < n; j++) {
                    if (i == j) continue; // 跳过基准点

                    if (points[i].equals(points[j])) {
                        duplicates++;
                        continue;
                    }

                    // 计算直线特征
                    LineFeature feature = getLineFeature(points[i], points[j]);
                    slopeCount.put(feature, slopeCount.getOrDefault(feature, 0) + 1);
                }

                // 找出当前基准点的最大共线点数
                int localMax = duplicates; // 包含重复点
                for (int count : slopeCount.values()) {
                    localMax = Math.max(localMax, count + duplicates);
                }

                maxPoints = Math.max(maxPoints, localMax);
            }

            return maxPoints;
        }

        private LineFeature getLineFeature(Point p1, Point p2) {
            LineFeature feature = new LineFeature();
            int dz = p2.z - p1.z;

            if (dz == 0) {
                feature.isParallelZ = true;
                feature.dx = feature.dy = 0;
            } else {
                feature.isParallelZ = false;
                feature.dx = (double) (p2.x - p1.x) / dz;
                feature.dy = (double) (p2.y - p1.y) / dz;
            }

            return feature;
        }
    }

    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++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            points[i] = new Point(x, y, z);
        }

        Solution solution = new Solution();
        System.out.println(solution.findMaxPoints(points));

        sc.close();
    }
}

class Point3D:
    def __init__(self, x=0, y=0, z=0):
        self.x = x
        self.y = y
        self.z = z
    
    def equal(self, pt):
        return self.x == pt.x and self.y == pt.y and self.z == pt.z

class Line3D:
    def __init__(self):
        self.kx = 0.0
        self.ky = 0.0
        self.bz = False
    
    def __eq__(self, other):
        return self.kx == other.kx and self.ky == other.ky and self.bz == other.bz
    
    def __lt__(self, other):
        return self.kx < other.kx or (self.kx == other.kx and self.ky < other.ky)

def maxPoints(points):
    maxNum = 0
    # 遍历所有点
    for i in range(len(points)):
        sameNum = 0  # 共线点个数
        ptMaxCount = 0
        lineMap = {}  # 存储直线,每一轮都要清空
        
        # 遍历除了i之外的其他点
        for j in range(i + 1, len(points)):
            p1 = points[i]
            p2 = points[j]
            
            # 两个点刚好相同
            if p1.equal(p2):
                sameNum += 1
                continue
            
            # 斜率相等三点共线
            line = Line3D()
            dz = p2.z - p1.z
            if dz == 0:
                line.bz = True
                line.kx = line.ky = 0
            else:
                line.bz = False
                line.kx = float(p2.x - p1.x) / dz
                line.ky = float(p2.y - p1.y) / dz
            
            # 计数
            key = (line.kx, line.ky, line.bz)  # 使用元组作为字典键
            if key not in lineMap:
                count = lineMap[key] = 1
            else:
                count = lineMap[key] = lineMap[key] + 1
            ptMaxCount = max(ptMaxCount, count)
        
        maxNum = max(ptMaxCount + sameNum + 1, maxNum)  # 最大共线数+与自己同坐标点+本身
    
    return maxNum

# 主函数
if __name__ == "__main__":
    n = int(input())
    points = []
    for _ in range(n):
        x, y, z = map(int, input().split())
        points.append(Point3D(x, y, z))
    print(maxPoints(points))