[CF1468F] Full Turn
Description
有 \(n\) 个人在二维平面直角坐标系上,第 \(i\) 个人初始站在 \((x_i,y_i)\),面向 \((u_i,v_i)\),现在所有人以相同的速度顺时针旋转,直到他们旋转完正好 \(360\deg\),我们认为两个人 \(i,j\) 进行了眼神接触仅当旋转的过程中有一个时刻满足 \(i\) 看向了 \(j\) 的同时 \(j\) 看向了 \(i\),求有多少对人会在旋转过程中进行至少一次眼神接触。
Solution
两个人能否进行眼神接触与位置无关,只取决于这两个人方向是否刚好相反
所以说缘分是逃不掉的,……,就这样
化简整数坐标表示的向量,然后塞进一个 map 里统计统计
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n;
cin >> n;
map<pair<int, int>, int> mp;
for (int i = 1; i <= n; i++)
{
int x, y, xx, yy;
cin >> x >> y >> xx >> yy;
x = xx - x;
y = yy - y;
int g = __gcd(x, y);
g = abs(g);
if (x && g)
x /= g;
if (y && g)
y /= g;
mp[{x, y}]++;
}
int ans = 0;
for (auto [pr, cnt] : mp)
{
auto [x, y] = pr;
int tmp = mp[{-x, -y}];
ans += tmp * cnt;
}
cout << ans / 2 << endl;
}
signed main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--)
solve();
}