给定二维空间中的四个点，我们需要找出它们是否构成平行四边形。
平行四边形有四条边。两条相对的边平行且长度相等。
例子：
点 = [(0, 0), (4, 0), (1, 3), (5, 3)]
以上点构成平行四边形。
点 = [(0, 0), (2, 0), (4, 0), (2, 2)]
以上点不构成平行四边形，因为前三个点本身是直线。
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
检查正方形和长方形的问题可以从正方形检查和长方形检查中读到，但在这个问题中，我们需要检查平行四边形。平行四边形的主要性质是平行四边形的对边平行且长度相等，并且平行四边形的对角线互相平分。我们使用第二个性质来解决这个问题。由于有四个点，我们可以通过考虑每一对得到总共 6 个中点。现在对于构成平行四边形的四个点，其中两个中点应该相等，其余中点应该不同。在下面的代码中，我们创建了一个映射，其中存储了与每个中点对应的对。计算出所有中点后，我们遍历了映射并检查每个中点的出现情况，如果恰好有一个中点出现了两次而另一个出现了一次，那么给定的四个点就构成了平行四边形，否则就不构成。
正方形检查：
JavaScript 检查给定的四个点是否形成正方形：JavaScript 检查给定的四个点是否形成正方形（Check if given four points form a square）-CSDN博客
C# 检查给定的四个点是否形成正方形：C# 检查给定的四个点是否形成正方形（Check if given four points form a square）-CSDN博客
Python 检查给定的四个点是否形成正方形：Python 检查给定的四个点是否形成正方形（Check if given four points form a square）-CSDN博客
Java 检查给定的四个点是否形成正方形：Java 检查给定的四个点是否形成正方形（Check if given four points form a square）-CSDN博客
C++ 检查给定的四个点是否形成正方形：C++ 检查给定的四个点是否形成正方形（Check if given four points form a square）-CSDN博客
长方形检查：
JavaScript 检查四条线段是否形成一个矩形：JavaScript 检查四条线段是否形成一个矩形（Check if four segments form a rectangle）-CSDN博客
C# 检查四条线段是否形成一个矩形：C# 检查四条线段是否形成一个矩形（Check if four segments form a rectangle）-CSDN博客
Python 检查四条线段是否形成一个矩形：Python 检查四条线段是否形成一个矩形（Check if four segments form a rectangle）-CSDN博客
Java 检查四条线段是否形成一个矩形：Java 检查四条线段是否形成一个矩形（Check if four segments form a rectangle）-CSDN博客
C++ 检查四条线段是否形成一个矩形：C++ 检查四条线段是否形成一个矩形（Check if four segments form a rectangle）-CSDN博客
示例代码：
// C# code to test whether four points make a
// parallelogram or not
using System;
using System.Collections.Generic;
// structure to represent a point
public struct Point
{
public double x, y;
public Point(double x, double y)
{
this.x = x;
this.y = y;
}
// defining operator < to compare two points
public static bool operator < (Point p1, Point p2)
{
if (p1.x < p2.x)
return true;
else if (p1.x == p2.x) {
if (p1.y < p2.y)
return true;
}
return false;
}
// defining operator > to compare two points
public static bool operator > (Point p1, Point p2)
{
if (p1.x > p2.x)
return true;
else if (p1.x == p2.x) {
if (p1.y > p2.y)
return true;
}
return false;
}
}
public class GFG {
// Utility method to return mid point of two points
static Point getMidPoint(Point[] points, int i, int j)
{
return new Point((points[i].x + points[j].x) / 2.0,
(points[i].y + points[j].y) / 2.0);
}
// method returns true if point of points array form
// a parallelogram
static bool isParallelogram(Point[] points)
{
Dictionary<Point, List<Point> > midPointMap
= new Dictionary<Point, List<Point> >();
// looping over all pairs of point to store their
// mid points
int P = 4;
for (int i = 0; i < P; i++) {
for (int j = i + 1; j < P; j++) {
Point temp = getMidPoint(points, i, j);
// storing point pair, corresponding to
// the mid point
if (midPointMap.ContainsKey(temp)) {
midPointMap[temp].Add(new Point(i, j));
}
else {
midPointMap[temp] = new List<Point>();
midPointMap[temp].Add(new Point(i, j));
}
}
}
int two = 0, one = 0;
// looping over (midpoint, (corresponding pairs))
// map to check the occurrence of each midpoint
foreach(var x in midPointMap)
{
// updating midpoint count which occurs twice
if (x.Value.Count == 2)
two++;
// updating midpoing count which occurs once
else if (x.Value.Count == 1)
one++;
// if midpoint count is more than 2, then
// parallelogram is not possible
else
return false;
}
// for parallelogram, one mid point should come
// twice and other mid points should come once
if (two == 1 && one == 4)
return true;
return false;
}
// Driver code to test above methods
static public void Main(string[] args)
{
Point[] points = new Point[4];
points[0] = new Point(0, 0);
points[1] = new Point(4, 0);
points[2] = new Point(1, 3);
points[3] = new Point(5, 3);
if (isParallelogram(points)) {
Console.WriteLine(
"Given points form a parallelogram");
}
else {
Console.WriteLine(
"Given points do not form a parallelogram");
}
}
}
// This code is contributed by prasad264
输出：
Given points form a parallelogram
时间复杂度： O(p²logp)，其中 p 是点的数量
辅助空间：O(p²)，其中 p 是点的数量
方法 2：使用向量：
• 另一种检查四个点是否构成平行四边形的方法是使用向量运算。我们可以计算由点对构成的向量，并检查它们是否满足平行四边形的性质。
• 以下是此方法的算法：
• 以A、B、C、D四个点作为输入。
• 使用公式 (B - A) 和 (D - C) 计算向量 AB 和 CD。
• 使用公式 (C - A) 和 (D - B) 计算向量 AC 和 BD。
• 通过计算 AB 和 CD 的叉积来判断它们是否平行。如果叉积为零，则它们平行。
• 通过计算AC和BD的叉积来判断它们是否平行。如果叉积为零，则它们平行。
• 如果 AB 和 CD 平行，且 AC 和 BD 平行，则这些点形成平行四边形。
以下是此方法的 C# 代码实现：
using System;
public struct Point
{
public double x, y;
public Point(double x, double y)
{
this.x = x;
this.y = y;
}
}
public class Parallelogram {
// Method to calculate the cross product of two vectors
public static double CrossProduct(Point a, Point b)
{
return a.x * b.y - a.y * b.x;
}
// Method to check if four points form a parallelogram
public static bool IsParallelogram(Point A, Point B,
Point C, Point D)
{
// Calculate vectors AB, CD, AC, and BD
Point AB = new Point(B.x - A.x, B.y - A.y);
Point CD = new Point(D.x - C.x, D.y - C.y);
Point AC = new Point(C.x - A.x, C.y - A.y);
Point BD = new Point(D.x - B.x, D.y - B.y);
// Check if AB and CD are parallel
if (CrossProduct(AB, CD) == 0) {
// Check if AC and BD are parallel
if (CrossProduct(AC, BD) == 0) {
// Points form a parallelogram
return true;
}
}
// Points do not form a parallelogram
return false;
}
public static void Main(string[] args)
{
Point A = new Point(0, 0);
Point B = new Point(4, 0);
Point C = new Point(1, 3);
Point D = new Point(5, 3);
if (IsParallelogram(A, B, C, D))
Console.WriteLine(
"Given points form a parallelogram");
else
Console.WriteLine(
"Given points do not form a parallelogram");
}
}
输出：
Given points form a parallelogram
时间复杂度：O(n^2logn)，其中 n 是点的数量
辅助空间：O(n^2)，因为地图数据结构用于存储中点，并且可以存储的最坏情况下的中点数量是 n^2。
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。