USACO 2020 February Contest Silver Division - Triangles

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We need to calculate for every \((x,y)\) the sum of all the areas of all triangles that have a right angle in that point, this can be done by calculating all the possible side lengths on its X-axis and its Y-axis this can be done in \(O(n)\) for all the dots on the same line (if the number of dots is \(n\)), using prefix sums.

Source code

The source code in C++ can be seen below.

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mod 1000000007
#define pii pair<ll, ll>
#define f first
#define s second

struct post{
    ll x, y, hsum, bsum;
};

int main() {
    freopen("triangles.in", "r", stdin);
    freopen("triangles.out", "w", stdout);

    int N; cin >> N;

    vector<post> posts(100006); 
    vector<vector<pii>> xs(2e4 + 1), ys(2e4 + 1);

    for(int i = 0; i < N; i++){
        cin >> posts[i].x >> posts[i].y;

        xs[posts[i].x + 10000].push_back({posts[i].y, i});
        ys[posts[i].y + 10000].push_back({posts[i].x, i});
    }

    for(int i = 0; i <= 20000; i++){
        if((int)xs[i].size() > 0){
            ll cur = 0;
            sort(xs[i].begin(), xs[i].end());

            for (int j = 1; j < (int)xs[i].size(); j++) {
                cur += (xs[i][j].f - xs[i][0].f);
            }

            posts[xs[i][0].s].hsum = cur;

            for(int j = 1; j < (int)xs[i].size(); j++){
                cur += ( -xs[i].size() + 2 * j) * ( xs[i][j].f - xs[i][j - 1].f);
                posts[xs[i][j].s].hsum = cur;
            }
        }
    }

    for(int i = 0; i <= 20000; i++){
        if((int)ys[i].size() > 0){
            ll cur = 0;
            sort(ys[i].begin(), ys[i].end());

            for (int j = 1; j < (int)ys[i].size(); j++) {
                cur += (ys[i][j].f - ys[i][0].f);
            }

            posts[ys[i][0].s].bsum = cur;

            for(int j = 1; j < (int)ys[i].size(); j++){
                cur += ( -ys[i].size() + 2 * j) * ( ys[i][j].f - ys[i][j - 1].f);
                posts[ys[i][j].s].bsum = cur;
            }
        }
    }

    ll ans = 0;
    for(int i = 0; i < N; i++) {
        ans += ((posts[i].hsum % mod) * (posts[i].bsum % mod)) % mod;
        ans %= mod;
    }

    cout << ans;
    return 0;
}