import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; class Point { int x; int y; int z; Point(int x, int y, int z) { this.x = x; this.y = y; this.z = z; } } /** * @author wylu */ public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); Point[] points = new Point[n]; for (int i = 0; i < n; i++) { String[] strs = br.readLine().split(" "); points[i] = new Point(Integer.parseInt(strs[0]), Integer.parseInt(strs[1]), Integer.parseInt(strs[2])); } System.out.println(maxPoints(points)); } private static int maxPoints(Point[] points) { if (points.length <= 2) return points.length; Map<Integer, Map<Integer, Map <Integer, Integer>>> map = new HashMap<>(); int res = 0; for (int i = 0; i < points.length; i++) { int overlap = 0, count = 0; for (int j = i + 1; j < points.length; j++) { int dx = points[i].x - points[j].x; int dy = points[i].y - points[j].y; int dz = points[i].z - points[j].z; if (dx == 0 && dy == 0 && dz == 0) { overlap++; continue; } int gcd = gcd(dx, dy, dz); dx /= gcd; dy /= gcd; dz /= gcd; if (map.containsKey(dx)) { if (map.get(dx).containsKey(dy)) { if (map.get(dx).get(dy).containsKey(dz)) { map.get(dx).get(dy).put(dz, map.get(dx).get(dy).get(dz) + 1); } else { map.get(dx).get(dy).put(dz, 1); } } else { Map<Integer, Integer> m = new HashMap<>(); m.put(dz, 1); map.get(dx).put(dy, m); } } else { Map<Integer, Integer> m1 = new HashMap<>(); m1.put(dz, 1); Map<Integer, Map<Integer, Integer>> m2 = new HashMap<>(); m2.put(dy, m1); map.put(dx, m2); } count = Math.max(count, map.get(dx).get(dy).get(dz)); } res = Math.max(res, count + 1 + overlap); map.clear(); } return res; } private static int gcd(int a, int b, int c) { return gcd(a, gcd(b, c)); } private static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } }
import java.util.*; public class Main { static class Point { int x; int y; int z; Point() {x = 0; y = 0; z = 0;} Point(int a, int b, int c) { x = a; y = b; z = c; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); Point[] points = new Point[n]; for (int i = 0; i < n; i++) points[i] = new Point(in.nextInt(), in.nextInt(), in.nextInt()); System.out.println(maxPoints(points)); } private static int maxPoints(Point[] points) { int n = points.length; if (n == 0) return 0; if (n <= 2) return n; int result = 0, overlap = 0, count = 0; HashMap<Integer, HashMap<Integer, HashMap<Integer, Integer>>> map = new HashMap<>(); for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { int dx = points[i].x - points[j].x; int dy = points[i].y - points[j].y; int dz = points[i].z - points[j].z; if (dx == 0 && dy == 0 && dz == 0) { overlap++; continue; } int gcd = gcd(dx, dy, dz); if (gcd != 0) { dx /= gcd; dy /= gcd; dz /= gcd; } if (map.containsKey(dx)) { if (map.get(dx).containsKey(dy)) { if (map.get(dx).get(dy).containsKey(dz)) { map.get(dx).get(dy).put(dz, map.get(dx).get(dy).get(dz) + 1); } else map.get(dx).get(dy).put(dz, 1); } else { HashMap<Integer, Integer> map1 = new HashMap<>(); map1.put(dz, 1); map.get(dx).put(dy, map1); } } else { HashMap<Integer, Integer> map1 = new HashMap<>(); HashMap<Integer, HashMap<Integer, Integer>> map2 = new HashMap<>(); map1.put(dz, 1); map2.put(dy, map1); map.put(dx, map2); } count = Math.max(count, map.get(dx).get(dy).get(dz)); } result = Math.max(result, count+overlap+1); map.clear(); overlap = 0; count = 0; } return result; } private static int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } private static int gcd(int a, int b, int c) { return gcd(gcd(a, b), c); } }
#include <iostream> #include <vector> #include <unordered_map> // 3维的点或者向量 struct Vec3{ int x; int y; int z; }; // 重载减法 static Vec3 operator-(const Vec3& p1, const Vec3& p2){ Vec3 v; v.x = p1.x - p2.x; v.y = p1.y - p2.y; v.z = p1.z - p2.z; return v; } // 最大公约数 int gcd(int a, int b){ if(b == 0) return a; return gcd(b, a%b); } int main(){ // 处理输入 int N; std::cin >> N; std::vector<Vec3> points(N); for(int i = 0; i < N; ++i){ std::cin >> points[i].x >> points[i].y >> points[i].z; } // 为自定义的Vec3提供“比较”运算以及“哈希”运算,不然无法作为哈希表中的key // 关于哈希的计算,这里也可以将Vec3中的3个数字连成string,将这个string当为哈希表的key。但可能超时。 auto equalOp = [](const Vec3& p1, const Vec3& p2){ return p1.x == p2.x && p1.y == p2.y && p1.z == p2.z; }; using h = std::hash<int>; auto hashOp = [](const Vec3& p){ // 模仿 boost::hash_combine size_t hashVal = 0; hashVal ^= h()(p.x) + 0x9e3779b9 + (p.x << 6) + (p.x >> 2); hashVal ^= h()(p.y) + 0x9e3779b9 + (p.y << 6) + (p.y >> 2); hashVal ^= h()(p.z) + 0x9e3779b9 + (p.z << 6) + (p.z >> 2); return hashVal; }; std::unordered_map<Vec3, int, decltype(hashOp), decltype(equalOp)> G(8, hashOp, equalOp); // 返回值 int res = 0; // 对向量的3个坐标约分的时候会使用到 std::vector<int> magic; // 遍历每一个点,计算以该点为起点的所有向量。如果发现两向量“相等”,则说明有共线存在。 for (int i = 0; i < N; ++i) { // 每更换一个起点,都要清空一次哈希表 G.clear(); // 记录最多有多少个点与起点共线(不考虑重合的点) int t = 0; // 单独考虑两点重合的情况 int overlap = 0; // 直接从i+1开始,而不是从0开始 // 考虑四个(互不重合)的点P1、P2、P3、P4。假设P2与P1共线,且我们最后得出P2、P3、P4三点共线,那么我们在之前以P1为起点的时候,肯定会得出 // 四点共线,即最大值肯定在前面的遍历中已经求得 for (int j = i + 1; j < N; ++j) { // 两点相减,形成向量 Vec3 v = points[j] - points[i]; // 如果重合,直接跳过 if (v.x == 0 && v.y == 0 && v.z == 0) { ++overlap; continue; } // 通过约分,将向量化为最简形式 // 考虑如向量v = (6, 2, 0),我们不能直接对这三个数求最大公约数K,再将这三个数除以K。因为K=0 // 这里只对所有非零的数求最大公约数 magic.clear(); if (v.x != 0) magic.push_back(v.x); if (v.y != 0) magic.push_back(v.y); if (v.z != 0) magic.push_back(v.z); int b = 1; if (magic.size() == 3) { b = gcd(magic[0], gcd(magic[1], magic[2])); } else if (magic.size() == 2) { b = gcd(magic[0], magic[1]); }else{ b = magic[0]; } v.x /= b; v.y /= b; v.z /= b; G[v] += 1; t = std::max(t, G[v]); } res = std::max(t + 1 + overlap, res); } std::cout << res; return 0; }
#include<bits/stdc++.h> using namespace std; class Point3D { public: int x, y, z; Point3D() : x(0), y(0), 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: float kx, ky; 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; cin >> n; vector<Point3D> points; while (n--) { Point3D p; cin >> p.x >> p.y >> p.z; points.push_back(p); } cout << maxPoints(points) << endl; return 0; }
#include<bits/stdc++.h> using namespace std; #define MAXN 2425 int n; struct PONIT { int x, y, z; PONIT() {} PONIT(int x, int y, int z) : x(x), y(y), z(z) {} bool operator<(const PONIT &A)const { return (x<A.x) || (x==A.x && y<A.y) || (x==A.x&&y==A.y && z<A.z); } }; PONIT points[MAXN]; int ***(int a, int b) { return b == 0 ? a : ***(b, a % b); } int ***(int a, int b, int c) { int ta = a < 0 ? -a : a; int tb = b < 0 ? -b : b; int tc = c < 0 ? -c : c; return ***(***(ta, tb), tc); } int main() { cin >> n; assert(n<2423); for (int i = 0; i < n; ++i) { scanf("%d%d%d", &points[i].x, &points[i].y, &points[i].z); } int ans = 0; for (int i = 0; i < n; ++i) { int cnt = 0, overlap = 0; map<PONIT, int> line; for (int j = i + 1; j < n; ++j) { int dx = points[i].x - points[j].x; int dy = points[i].y - points[j].y; int dz = points[i].z - points[j].z; if (dx == 0 && dy == 0 && dz == 0) { overlap++; continue; } int g = ***(dx, dy, dz); if(dx<0|| (dx==0 && dy<0) || (dx==0 && dy==0 && dz<0))g=-g;//统一向量的方向 dx /= g; dy /= g; dz /= g; ++line[PONIT(dx,dy,dz)]; cnt = max(cnt, line[PONIT(dx, dy, dz)]); } line.clear(); ans = max(ans, cnt + overlap + 1); } printf("%d\n", ans); return 0; }