2018 年腾讯校招笔试题 判断平面上四个点是否构成正方形
程序员文章站
2022-03-02 10:54:48
...
小Q搜寻了整个魔法世界找到了四块魔法石所在地,当4块魔法石正好能构成一个正方形的时候将启动魔法阵,小Q就可以借此实现一个愿望。
现在给出四块魔法石所在的坐标,小Q想知道他是否能启动魔法阵
输入描述:
输入的第一行包括一个整数(1≤T≤5)表示一共有T组数据 每组数据的第一行包括四个整数x[i](0≤x[i]≤10000),即每块魔法石所在的横坐标 每组数据的第二行包括四个整数y[i](0≤y[i]≤10000),即每块魔法石所在的纵坐标
输出描述:
对于每组数据,如果能启动魔法阵输出“Yes”否则输出“No”。
示例1
输入
3 0022 0202 0156 1605 0077 0303
输出
Yes Yes No
思路: 这道题目的输入有一点复杂,需要注意处理下
判断四个点是否构成正方形, 首先将点按照从左到右
从下到上排序。然后判断四条边相等,并且有一个角是
直角,判断角度为直角可以用向量内积判断。
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
struct Point
{
int x,y;
// 按x从小到大排序, 如果x相等, 按y从小到大排序
bool operator < (Point &a){
if(x!=a.x) return x<a.x;
else return y<a.y;
}
};
double TwoPointDistance(Point& a, Point& b)//计算两点之间的距离
{
return sqrt(pow((a.x - b.x), 2) + pow((a.y - b.y), 2));
}
bool IsRightAngle(Point& a, Point& b, Point& c)//判断是否为直角
{
double x;
x = (a.x - b.x)* (a.x - c.x) + (a.y - b.y)*(a.y - c.y);
if (x == 0)
return 1;
else
return 0;
}
int main()
{
int T;
cin>>T;
while(T--){
Point p[4];
string x,y;
cin>>x;
cin>>y;
for(int i=0;i<4;i++) p[i].x = x[i]-'0';
for(int i=0;i<4;i++) p[i].y = y[i]-'0';
sort(p,p+4);
double s1 = TwoPointDistance(p[0], p[2]);
double s2 = TwoPointDistance(p[0], p[1]);
double s3 = TwoPointDistance(p[3], p[1]);
double s4 = TwoPointDistance(p[2], p[3]);
if(s1 == s2 && s2 == s3 && s3 == s4 && s1 != 0 && IsRightAngle(p[0], p[1], p[2])){
cout<<"Yes"<<endl;
}
else cout<<"No"<<endl;
}
}