2022-09-20 乐帮网
数学
我们得到四个段作为它们端点的一对坐标。 我们需要判断这四个线段是否构成一个矩形。
例子:
Input : segments[] = [(4, 2), (7, 5),
(2, 4), (4, 2),
(2, 4), (5, 7),
(5, 7), (7, 5)]
Output : Yes
Given these segment make a rectangle of length 3X2.
Input : segment[] = [(7, 0), (10, 0),
(7, 0), (7, 3),
(7, 3), (10, 2),
(10, 2), (10, 0)]
Output : Not
These segments do not make a rectangle.
Above examples are shown in below diagram.
这个问题主要是如何检查给定的四个点是否形成正方形的扩展。
我们可以通过使用矩形的属性来解决这个问题。 首先,我们检查线段的唯一端点总数,如果这些点的数量不等于 4,则线段不能构成矩形。 然后我们检查所有点对之间的距离,最多应该有 3 个不同的距离,一个是对角线,两个是边,最后我们将检查这三个距离之间的关系,对于制作矩形的线段,这些距离应该 满足毕达哥拉斯关系,因为矩形的边和对角线构成直角三角形。 如果它们满足上述条件,那么我们会将由线段制成的多边形标记为矩形,否则不会。
C++
// C++ program to check whether it is possible
// to make a rectangle from 4 segments
#include <bits/stdc++.h>
using namespace std;
#define N 4
// structure to represent a segment
struct Segment
{
int ax, ay;
int bx, by;
};
// Utility method to return square of distance
// between two points
int getDis(pair<int, int> a, pair<int, int> b)
{
return (a.first - b.first)*(a.first - b.first) +
(a.second - b.second)*(a.second - b.second);
}
// method returns true if line Segments make
// a rectangle
bool isPossibleRectangle(Segment segments[])
{
set< pair<int, int> > st;
// putting all end points in a set to
// count total unique points
for (int i = 0; i < N; i++)
{
st.insert(make_pair(segments[i].ax, segments[i].ay));
st.insert(make_pair(segments[i].bx, segments[i].by));
}
// If total unique points are not 4, then
// they can't make a rectangle
if (st.size() != 4)
return false;
// dist will store unique 'square of distances'
set<int> dist;
// calculating distance between all pair of
// end points of line segments
for (auto it1=st.begin(); it1!=st.end(); it1++)
for (auto it2=st.begin(); it2!=st.end(); it2++)
if (*it1 != *it2)
dist.insert(getDis(*it1, *it2));
// if total unique distance are more than 3,
// then line segment can't make a rectangle
if (dist.size() > 3)
return false;
// copying distance into array. Note that set maintains
// sorted order.
int distance[3];
int i = 0;
for (auto it = dist.begin(); it != dist.end(); it++)
distance[i++] = *it;
// If line seqments form a square
if (dist.size() == 2)
return (2*distance[0] == distance[1]);
// distance of sides should satisfy pythagorean
// theorem
return (distance[0] + distance[1] == distance[2]);
}
// Driver code to test above methods
int main()
{
Segment segments[] =
{
{4, 2, 7, 5},
{2, 4, 4, 2},
{2, 4, 5, 7},
{5, 7, 7, 5}
};
(isPossibleRectangle(segments))?cout << "Yes\n":cout << "No\n";
}
JavaScript:
// JavaScript program to check whether it is possible
// to make a rectangle from 4 segments
const N = 4;
// Utility method to return square of distance
// between two points
function getDis(a, b)
{
return (parseInt(a[0]) - parseInt(b[0]))*(parseInt(a[0]) - parseInt(b[0])) + (parseInt(a[1]) - parseInt(b[1]))*(parseInt(a[1]) - parseInt(b[1]));
}
// method returns true if line Segments make
// a rectangle
function isPossibleRectangle(segments)
{
let st = new Set();
// putting all end points in a set to
// count total unique points
for (let i = 0; i < N; i++)
{
let tmp1 = [segments[i][0], segments[i][1]];
let tmp2 = [segments[i][2], segments[i][3]];
st.add(tmp1.join(''));
st.add(tmp2.join(''));
}
// If total unique points are not 4, then
// they can't make a rectangle
if (st.size != 4)
{
return false;
}
// dist will store unique 'square of distances'
let dist = new Set();
// calculating distance between all pair of
// end points of line segments
for(let it1 of st)
{
for(let it2 of st)
{
if(it1 !== it2)
{
dist.add(getDis(it1.split(''), it2.split('')));
}
}
}
// if total unique distance are more than 3,
// then line segment can't make a rectangle
if (dist.size > 3)
{
return false;
}
// copying distance into array. Note that set maintains
// sorted order.
let distance = new Array();
for (let x of dist)
{
distance.push(x);
}
// If line seqments form a square
if (dist.size === 2)
{
return (2*distance[0] == distance[1]);
}
// distance of sides should satisfy pythagorean
// theorem
return (distance[0] + distance[1] == distance[2]);
}
// Driver code to test above methods
{
let segments = [
[4, 2, 7, 5],
[2, 4, 4, 2],
[2, 4, 5, 7],
[5, 7, 7, 5] ]
if(isPossibleRectangle(segments)){
console.log("Yes");
}
else{
console.log("No");
}
}
// The code is contributed by Nidhi Goel
https://www.geeksforgeeks.org/check-four-segments-form-rectangle/?ref=lbp
关注我的微信公众号
在公众号里留言交流
投稿邮箱:1052839972@qq.com
庭院深深深几许?杨柳堆烟,帘幕无重数。
玉勒雕鞍游冶处,楼高不见章台路。
雨横风狂三月暮。门掩黄昏,无计留春住。
泪眼问花花不语,乱红飞过秋千去。
如果感觉对您有帮助
欢迎向作者提供捐赠
这将是创作的最大动力