欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
    }

}