593. Valid Square
Problem statement:
Given the coordinates of four points in 2D space, return whether the four points could construct a square.
The coordinate (x,y) of a point is represented by an integer array with two integers.
Example:
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True
Note:
- All the input integers are in the range [-10000, 10000].
- A valid square has four equal sides with positive length and four equal angles (90-degree angles).
- Input points have no order.
Solution one: a set to find the relative of four points(AC).
As the second problem in this contest, the key points are to find the right order of these four points and check the if one/two/three/fours points are overlapped. It will be very easier if we know the relative positions of these four points. The answer comes out to check the length of four sides and two diagonals.
I use the default sorting characteristic of a set instead of designing an algorithm to find their relative positions.
The final order after sorting by a set is 0, 1, 3, 2 in counterclockwise.
The efficiency does not matter in this problem, correctness is on the top.
class Solution {
public:
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
vector<vector<int>> points(, vector<int>(, ));
set<vector<int>> points_set;
points_set.insert(p1);
points_set.insert(p2);
points_set.insert(p3);
points_set.insert(p4);
if(points_set.size() != ){
return false;
}
int idx = ;
for(auto point : points_set){
points[idx] = point;
idx++;
}
if( dis_square(points[], points[]) == dis_square(points[], points[])
&& dis_square(points[], points[]) == dis_square(points[], points[])
&& dis_square(points[], points[]) == dis_square(points[], points[])
&& dis_square(points[], points[]) == dis_square(points[], points[])
&& dis_square(points[], points[]) == dis_square(points[], points[])){
return true;
}
return false;
}
private:
int dis_square(vector<int> p1, vector<int> p2){
return (p1[] - p2[]) * (p1[] - p2[]) + (p1[] - p2[]) * (p1[] - p2[]);
}
};
Solution two: STL sort algorithm(AC). This is concise and easy to understand(Better).
Another good alternative approach to find the relative position of these four points are the sort algorithm in STL.
The default sorting algorithm sort the first element and sort the second element. The sorted order is still 0, 1, 3, 2 in counterclockwise.
But, we need to check if one or more positions are overlapped before sorting.
class Solution {
public:
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
// check if one or more points are overlapped
if(p1 == p2 || p1 == p3 || p1 == p4 || p2 == p3 || p2 == p4 || p3 == p4){
return false;
}
vector<vector<int>> points = {p1, p2, p3, p4};
sort(points.begin(), points.end());
if(dis_square(points[], points[]) == dis_square(points[], points[]) // check four sides
&& dis_square(points[], points[]) == dis_square(points[], points[])
&& dis_square(points[], points[]) == dis_square(points[], points[])
&& dis_square(points[], points[]) == dis_square(points[], points[])
// check the diagonals
&& dis_square(points[], points[]) == dis_square(points[], points[])){
return true;
}
return false;
}
private:
int dis_square(vector<int> p1, vector<int> p2){
return (p1[] - p2[]) * (p1[] - p2[]) + (p1[] - p2[]) * (p1[] - p2[]);
}
};
最新文章
- Webservice 65535 错误
- C语言 自动修改文件名小程序
- p4 是否能自动merge
- E2 2014.6.3 更新日志
- BZOJ 1005: [HNOI2008]明明的烦恼 Purfer序列 大数
- mysql中使用count()统计的特殊之处
- 20160327javaweb 之JSP入门
- 【转】android UI进阶之实现listview中checkbox的多选与记录--不错
- 对Big O的新的认识
- shell中break 与 continue
- 再起航，我的学习笔记之JavaScript设计模式05(简单工程模式)
- [Swift]LeetCode605. 种花问题 | Can Place Flowers
- Python手记（二）
- vue和webpack打包 项目相对路径修改
- mysql 解锁
- dom4j 通过 org.dom4j.DocumentFactory 设置命名空间来支持 带namespace 的 xpath
- Cisco交换机堆叠与HSRP之间的区别
- VLC简介及使用说明
- 关于easyUI分页
- 修改数据库的instance_name和db_name