[56]直线上的点-吉比特2018秋

1.题目描述

给定N个三维坐标点(包含整形x,y,z)，找到位于同一条直线上点的最大个数。

• 输入说明：
  第一行输入坐标点的个数N，第2~N+1行输入N个点(格式为x y z)，0<N<2000; -10000<x,y,z<10000
• 输入示例：

  4 
  0 0 0 
  1 1 1
  -1 -1 -1 
  0 1 0
  

• 输出示例：

  3 
  

2.题目解析

• 解题思路
  两个点决定一条直线，所以两层遍历，可以遍历所有直线，并在遍历的过程中，把直线缓存起来，下次再遇到的相同直线时候就只是把这条直线对应的存在的点的个数累加。这样我们就可以算出经过某个点的某条直线上最多的点的个数。要注意的是第二层遍历的时候，可以只遍历从i + 1 ~ size – 1的直线，因为与之前的点能够组成的直线已经处理过，不需要再处理(a,b决定的直线和 b,a决定的直线是一样的)。
  注意：两点相同也算共线。
  共线算法是关键。
  两点式：空间两个点确定一条直线。
  已知两个点和，那么过这两点的直线两点式方程为
  
  可以变成两个式子和
  分子分母交换位置可得和

其中和是定值，只要第三个点满足上面的式子即三点共线。
注意，当时，，不能做分母，需要特殊处理。

3.参考答案

#include <bits/stdc++.h>
using namespace std;
class Point3D {
public:
  int x, y, z;
  Point3D(){x=y=z=0;}
  Point3D(int a, int b, int c){x=a;y=b;z=c;}
  bool equal(const Point3D& pt) const{
      return x == pt.x && y == pt.y && z == pt.z;
  }
};
class Line3D {
public:
  // dx / dz
  float kx;
  // dy / dz
  float ky;
  // dz == 0 ?
  bool bz;
  bool operator==(const Line3D &l) const {
    return kx == l.kx && ky == l.ky && bz == l.bz;
  }
  bool operator<(const Line3D &l) const {
    return kx < l.kx || (kx == l.kx && ky < l.ky);
  }
};
int maxPoints(vector<Point3D> points) {
  int maxNum = 0;
  for (size_t i = 0; i < points.size(); ++i) {// 遍历所有点
    int sameNum = 0;
    int ptMaxCount = 0;
    map<Line3D,int> lineMap;
    for (size_t j = i + 1; j < points.size(); ++j) {// 遍历除了i之外的其他点
      auto &p1 = points[i];
      auto &p2 = points[j];
      
      if (p1.equal(p2)) { // 两个点刚好相同
        sameNum++;
        continue;
      }
      
      // 斜率相等三点共线
      Line3D line;
      int 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;
      }
        
      // 计数
      int count;
      if (lineMap.find(line) == lineMap.end())
        count = lineMap[line] = 1;
      else
        count = ++lineMap[line];
      
      ptMaxCount = max(ptMaxCount, count);
    }
    // 
    maxNum = max(ptMaxCount + sameNum + 1, maxNum);
  }
  return maxNum;
}
int main(){
    int n = 0;
    scanf("%d",&n);
    vector<Point3D> points;
    while(n--){
        Point3D p;
        scanf("%d%d%d",&p.x,&p.y,&p.z);
        points.push_back(p);
    }
    printf("%d\n",maxPoints(points));
}

牛客题目