[编程题]直线上的点
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);
}
}
编辑于 2019-03-11 00:45:05
回复(0)
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);
}
}
编辑于 2018-09-03 15:06:28
回复(0)
#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;
} 思路同leetcode-149。题149是二维点，这道题是3维点。如果采用方向向量来判断共线，则两道题几乎一样。
细节：如果用哈希表存方向向量，需要自定义哈希。简单地将各数据域拼接成string，再做key的话，可能会超时。
发表于 2021-08-07 17:55:57
回复(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;
} 参考简书上的题解
发表于 2021-04-06 20:31:40
回复(0)
首先，这道题很坑，n<2000的假设不成立，试出来好像n有个2422的值。
方法：
一、固定一个点P，扫描其他点和P的连线，若PA和PB斜率相同，则PAB共线。重复点等细节自己考虑。
二、直线的斜率用向量( dx/***(dx,dy,dz),...,... )标识，由***的性质保证向量与直线的对应关系（需要处理一下正负号，点都是整数点，可以自己画一画验证性质）。
复杂度：O(n2X)。扫描了每条直线，一共组合数Cn2条直线。每条直线的处理挺复杂的，有***和map，不过***很快，map的摊还代价也不是很高。
#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;
}
发表于 2020-07-15 17:23:37
回复(1)
问题信息
通过挑战的用户
查看代码-
2022-10-07 18:34:44
-
2022-09-09 01:21:13
-
2022-09-03 09:52:49
-
2022-09-02 02:45:48
-
2022-08-30 20:23:40
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
