Submission #68351274

---

Source Code Expand

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<ll> x(n), y(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
    }
    map<pair<ll, ll>, ll> mp;
    map<tuple<ll, ll, ll, ll>, ll> mp2;
    ll res = 0, res2 = 0;
    auto calc = [&](ll x1, ll y1, ll x2, ll y2) -> pair<ll, ll> {
        if (x1 == x2) return {0, 1};
        if (y1 == y2) return {1, 0};
        if (x1 > x2) {
            swap(x1, x2);
            swap(y1, y2);
        }
        ll dx = x2 - x1, dy = y2 - y1;
        ll g = __gcd(abs(dx), abs(dy));
        dx /= g, dy /= g;
        return {dx, dy};
    };
    vector<pair<ll, ll>> v1;
    vector<tuple<ll, ll, ll, ll>> v2;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            ll x1 = x[i], y1 = y[i];
            ll x2 = x[j], y2 = y[j];
            auto [dx, dy] = calc(x1, y1, x2, y2);
            //            cout << "(" << x1 << ", " << y1 << ") to (" << x2 << ", " << y2 << ") => " << dx << ", " << dy << endl;
            v1.emplace_back(dx, dy);
            v2.emplace_back(dx, dy, abs(x1 - x2), abs(y1 - y2));
            //            res += mp[{dx, dy}];
            //            res2 += mp2[{dx, dy, abs(x1 - x2), abs(y1 - y2)}];
            //            mp[{dx, dy}]++;
            //            mp2[{dx, dy, abs(x1 - x2), abs(y1 - y2)}]++;
        }
    }
    //    cout << res << endl;
    //    cout << res2 << endl;
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    for (int i = 0; i < v1.size();) {
        int cnt = 0;
        auto cp = v1[i];
        while (i < v1.size() && v1[i] == cp) {
            cnt++;
            i++;
        }
        res += (ll)cnt * (cnt - 1) / 2;
    }
    for (int i = 0; i < v2.size();) {
        int cnt = 0;
        auto cp = v2[i];
        while (i < v2.size() && v2[i] == cp) {
            cnt++;
            i++;
        }
        res2 += (ll)cnt * (cnt - 1) / 2;
    }
    cout << res - res2 / 2 << endl;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:54:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   54 |     for (int i = 0; i < v1.size();) {
      |                     ~~^~~~~~~~~~~
Main.cpp:57:18: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   57 |         while (i < v1.size() && v1[i] == cp) {
      |                ~~^~~~~~~~~~~
Main.cpp:63:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::tuple<long long int, long long int, long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   63 |     for (int i = 0; i < v2.size();) {
      |                     ~~^~~~~~~~~~~
Main.cpp:66:18: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::tuple<long long int, long long int, long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   66 |         while (i < v2.size() && v2[i] == cp) {
      |                ~~^~~~~~~~~~~

Judge Result