向量

题目描述

给你n个向量，请问是否可以通过旋转异或伸缩任意一个向量，使得这n个向量相加等于0向量。

注意，在本题中，我们认为0向量只能伸缩为0向量，非0向量可以伸缩为0向量、方向相同长度任意的向量、方向相反长度任意的向量。

输入

单组输入

第一行一个正整数 $n(1\le n\le 10^5)$，即向量的个数。

接下来$n$行，每行两个整数$x_i$, $y_i$ $(0\le |x_i|,|y_i|\le 10^9)$，分别代表第$i$个向量$x$轴与$y$轴的大小方向。

数据保证

\[\sum_{i=1}^{n}(|x_i|+|y_i|)\le 10^9 \]

输出

若存在满足要求的操作输出 “yes”，反之输出 “no”。

样例

样例输入	样例输出
3 0 0 1 2 4 2	no

AC代码

#include <iostream>
#include <cstdio>
typedef long long ll;
#define MAXN 100005

using namespace std;

struct Vec
{
    ll x;
    ll y;
};


Vec vec[MAXN];

int main(){
    int n;
    cin>>n;
    Vec allSum;
    allSum.x=0;allSum.y=0;
    for(int i=1;i<=n;i++){
        cin>>vec[i].x>>vec[i].y;
        allSum.x+=vec[i].x;
        allSum.y+=vec[i].y;
    }
    ll ans = 0;
    for(int i=1;i<=n;i++){
        if(vec[i].x==0&&vec[i].y==0) continue;
        Vec tmpSum = allSum;
        tmpSum.x-=vec[i].x;
        tmpSum.y-=vec[i].y;
        ll dis1 = tmpSum.x*tmpSum.x+tmpSum.y*tmpSum.y;
        ll dis2 = vec[i].x*vec[i].x+vec[i].y*vec[i].y;
        if(dis1==dis2) {
            ans=1;
            break;
        }
        if(vec[i].y*tmpSum.x-tmpSum.y*vec[i].x==0) {
            ans=1;
            break;
        }
    }
    if(ans) cout<<"yes";
    else cout<<"no";
    return 0;
}

正确性证明

首先分析题目，出题人的表达和数据结果并不一致。“是否可以通过旋转异或伸缩任意一个向量”实际上应该是“是否可以通过旋转异或伸缩某一个向量”，从而“使得这n个向量相加等于0向量”。

数据也就$10^5$，直接枚举就行。先将所有向量加到一起记为allSum，然后建立一个tmpSum = allSum-我们当前枚举的向量，记为v。

然后判断这个tmpSum向量是否和v长度平方相等，是则可以通过旋转v，再相加得到0向量。判断tmpSum向量终点是否和$(0,0)$和v的终点在同一直线上,是则可以通过伸缩v来达到目的。这里判断三点共线的方法是求外积。若都为否，则不可以只对v伸缩或者旋转达到目的，枚举下一个。这里注意，我上述写的代码要将0向量略过，否则0向量总是可以通过三点共线的判断，达不到目的。

如果枚举出一个向量可以达到目的，就输出yes。如果所有向量都达不到目的，就输出no。