[CF1468F] Full Turn - 结论

[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();
}
上一篇:mysql使用group by查询报错SELECT list is not in GROUP BY clause and contains nonaggregated column...解决方案


下一篇:DAG-GNN: DAG Structure Learning with Graph Neural Networks