Full Turn
题意
给你 n个人的位置和他们眼睛看的方向 这 n 个人同时开始顺时针旋转 360° 问 ：在旋转过程中 有多少对人进行了眼神接触
思路
将 一个人的位置看成向量的起点 他看向的位置看成向量的终点 构造出一个向量然后对这个向量进行归一化
注意：不能将其标准化 即横纵坐标同时除以其长度 因为在 map 中 只要有一点误差就会被当作两个不同的数据 最终会导致我们得到的答案比正确答案少 为了避免这种情况发生 我们用 横纵坐标的gcd 对其进行归一化
一个人能在旋转中和别人进行眼神接触的数量为其对应的向量的负向量个数
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } const int N = 200010; LL n; void solve() { scanf("%lld", &n); LL res = 0; map<pair<double, double>, LL>mp; LL x, y, u, v; for (int i = 1; i <= n; ++i) { scanf("%lld%lld%lld%lld", &x, &y, &u, &v); LL a = (u - x); LL b = (v - y); LL g = gcd(abs(a), abs(b)); a /= g; b /= g; //cout << "a == " << a << " " <<"b == " << b << endl; mp[{a, b}]++; res += mp[{-a, -b}]; } printf("%lld\n", res); } int main() { int t; cin >> t; while(t--) solve(); return 0; }
