憧憬

NC229174. 憧憬

描述

(本场比赛题目背景均不影响题意理解，可直接跳过）

但愿这漫天时起时落的星斗

曾照拂过的人们都能被庇佑

在颠沛之中漂流于不经意的时候

你会与你的梦悄然邂逅

——周深《请笃信一个梦》

小P在文化课中遇到了这样一道题，爱好编程的他将3个向量的题目推广到了n个向量，快来帮帮他！

给定n个向量的起点和终点x1,y1,x2,y2,再给出一个目标向量，求能否由n个向量中的两个相加构造出一个与目标向量平行的向量（注意，平行包括方向相同或相反）

保证 $x1\ne x2$ $y1 \ne y2$ ，保证两个向量相加不为零向量

输入描述

第一行给定一个整数n
接下来n行每行四个整数x1,y1,x2,y2，表示第i个向量的起点和终点
最后一行给出四个整数x1,y1,x2,y2，表示目标向量的起点和终点

输出描述

若可以，输出“YES”
否则输出“NO”（均不含引号）

示例1

输入:

输出:

YES

说明:

1号向量与3号向量相加

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 5ms, 内存消耗: 488K, 提交时间: 2021-10-25 20:43:51

#include<bits/stdc++.h>
using namespace std;
int n;
int x[1010],y[1010];
int main(){
	cin>>n;
	for(int i=0;i<=n;i++){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		x[i]=c-a;
		y[i]=d-b;
	}
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if((x[i]+x[j])*y[n]==(y[i]+y[j])*x[n]){
				cout<<"YES";
				return 0;
			}
		}
	}
	cout<<"NO";
	return 0;
}

Python3 解法, 执行用时: 319ms, 内存消耗: 4668K, 提交时间: 2022-09-19 16:00:16

n=int(input())
x=[]
y=[]
for _ in range(n+1):
    x1,y1,x2,y2=map(int,input().split())
    x.append(x2-x1)
    y.append(y2-y1)

for i in range(n):
    for j in range(i+1,n):
        if (y[j]+y[i])*x[-1]==y[-1]*(x[j]+x[i]):
            print('YES')
            exit(0)
print('NO')