当前位置：首页 > article >正文

Java 覆盖所有点的最少线数（Minimum lines to cover all points）

article 2024/10/22 19:14:54

示例图1

示例图2

给定二维空间中的 N 个点，我们需要打印经过所有这 N 个点并且也经过特定 (xO, yO) 点的最少线数。

示例：

如果给定的点为 (-1, 3), (4, 3), (2, 1), (-1, -2), (3, -3) 且 (xO, yO) 点为 (1, 0)，即每条线都必须经过此点。那么我们必须绘制至少两条线来覆盖所有经过 (xO, yO) 的点。

我们可以通过考虑所有点的斜率（xO，yO）来解决这个问题。如果两个不同的点的斜率（xO，yO）相同，那么它们可以用同一条线覆盖，这样我们就可以跟踪每个点的斜率，每当我们得到一个新的斜率时，我们就将线数增加一。

在下面的代码中，斜率被存储为一对整数以消除精度问题，并使用一个集合来跟踪发生的斜率。请参阅下面的代码以更好地理解。

示例代码：

// Java Program for above approach
import java.io.*;
import java.util.*;
import java.util.Set;

// User defined Pair class
class Pair {
int x;
int y;

// Constructor
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}

class GFG {
// Utility method to get gcd of a and b
public static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// method returns reduced form of dy/dx as a pair
public static Pair getReducedForm(int dy, int dx)
{
int g = gcd(Math.abs(dy), Math.abs(dx));

// get sign of result
boolean sign = (dy < 0) ^ (dx < 0);
Pair res = new Pair(0, 0);

if (sign) {
res.x = -Math.abs(dy) / g;
res.y = Math.abs(dx) / g;
}
else {
res.x = Math.abs(dy) / g;
res.y = Math.abs(dx) / g;
}
return res;
}

/* method returns minimum number of lines to
cover all points where all lines goes
through (xO, yO) */

public static int minLinesToCoverPoints(int points[][],
int N, int xO,
int yO)
{
// set to store slope as a string
Set<String> st = new HashSet<String>();

Pair temp;
int minLines = 0;

// loop over all points once
for (int i = 0; i < N; i++) {
// get x and y co-ordinate of current point
int curX = points[i][0];
int curY = points[i][1];

temp = getReducedForm(curY - yO, curX - xO);

// convert pair into string to store in set
String tempString = temp.x + "," + temp.y;

// if this slope is not there in set,
// increase ans by 1 and insert in set

if (st.contains(tempString) == false) {
st.add(tempString);
minLines += 1;
}
}

return minLines;
}

// Driver code
public static void main(String[] args)
{
int xO, yO;
xO = 1;
yO = 0;

int points[][] = { { -1, 3 },
{ 4, 3 },
{ 2, 1 },
{ -1, -2 },
{ 3, -3 } };

int N = points.length;
System.out.println(
minLinesToCoverPoints(points, N, xO, yO));
}
}

// This code is contributed by rj13to.