魔法阵

[编程题]魔法阵

热度指数：3919 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小Q搜寻了整个魔法世界找到了四块魔法石所在地，当4块魔法石正好能构成一个正方形的时候将启动魔法阵，小Q就可以借此实现一个愿望。

现在给出四块魔法石所在的坐标，小Q想知道他是否能启动魔法阵

输入描述:

输入的第一行包括一个整数（1≤T≤5）表示一共有T组数据

每组数据的第一行包括四个整数x[i](0≤x[i]≤10000)，即每块魔法石所在的横坐标

每组数据的第二行包括四个整数y[i](0≤y[i]≤10000),即每块魔法石所在的纵坐标

输出描述:

对于每组数据，如果能启动魔法阵输出“Yes”否则输出“No”。

示例1

输入

输出

Yes
Yes
No

算法知识视频讲解

Python

牛客817844335号

import sys
group_num = None
group = []
temp = []

for line in sys.stdin:
if group_num is None:
group_num = int(line.strip('\n'))
else:
temp.append(list(map(int,list(line.strip('\n')))))
if len(temp)==2:
group = (list(zip(temp[0],temp[1])))
d = []
for i in range(1,len(group)):
d0 = pow(group[i][0]-group[0][0],2)+pow(group[i][1]-group[0][1],2)
if not d0 in d:
d.append(d0)
if not len(d) == 2:
print('No')
elif not max(d) == 2*min(d):
print('No')
else:
print('Yes')
temp = []

发表于 2020-09-06 17:11:01 回复(0)

Python

白色纯度

判断有三个等腰直角三角形即可。时间上也没那么复杂，算比较高效了。

思路：

对于给定的四个坐标点，每次只用其中的三个坐标，然后求出三条边的边长，排序后，判定较小的两条边是否相等并且最长的边是否是前两个边的和。切记，给的四个点，共有四个等腰直角三角形，等腰直角三角形的判定至少要有三次，因为两次的结果也有可能是60度的菱形。

def sanjiao(x,y):
    x = [int(i) for i in x]
    y = [int(j) for j in y]
    length = []
    for i in range(1,len(x)):
        temp = (x[i]-x[i-1])**2+(y[i]-y[i-1])**2
        length.append(temp)
    t = (x[2]-x[0])**2+(y[2]-y[0])**2
    length.append(t)
    length.sort()
    if length[0]==length[1] and length[0]+length[1]==length[-1]:
        return True
    return False
if __name__=='__main__':
    n = int(input().strip())
    for _ in range(n):
        x = input().strip()
        y = input().strip()
        t1 = sanjiao(x[:3],y[:3])
        t2 = sanjiao(x[1:],y[1:])
        t3 = sanjiao(x[2:]+x[0],y[2:]+y[0])
        if t1 and t2 and t3:
            print('Yes')
        else:
            print('No')

发表于 2019-09-10 19:30:05 回复(0)

Python

体重不增到120不改名

思路：

正方形的判定条件：每个点的临边、对角线长度相等，也就是，每个点到其它三点距离的降（升）序排列相同

import sys
n=int(input())
res=[]
for i in range(n):
    x=[int(i) for i in input()]
    y=[int(i) for i in input()]
    D=[]
    suc=0
    for j in range(4):
        d1=(x[(j+1)%4]-x[j])**2+(y[(j+1)%4]-y[j])**2
        d2=(x[(j+2)%4]-x[j])**2+(y[(j+2)%4]-y[j])**2
        d3=(x[(j+3)%4]-x[j])**2+(y[(j+3)%4]-y[j])**2
        if len(D):
            D=[d1,d2,d3]
            D.sort()
        else:
            D_=[d1,d2,d3]
            D_.sort()
            if not D==D_:
                break
        suc+=1
    if suc==4:
        print("Yes")
    else:
        print("No")

发表于 2019-03-09 16:34:16 回复(0)