USACO 2020 February Contest Bronze Division - Triangles

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can brute force the triangles and find the max area.

Source codes

The source codes in C++ and Python can be seen below.

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

int main()
{
    ifstream cin("triangles.in");
    ofstream cout("triangles.out");

    int n;
    cin >> n;

    vector<pair<int, int> > vp(n+1);
    for(int i = 1; i <= n; i++)
        cin >> vp[i].first >> vp[i].second;

    long long ans = 0;
    for(int i = 1; i <= n; i++)
        for(int j = i+1; j <= n; j++)
            for(int k = j+1; k <= n; k++)
            {
                if(vp[i].first == vp[j].first && vp[j].second == vp[k].second)
                    ans = max(ans, 1LL * abs(vp[j].second - vp[i].second) * abs(vp[k].first - vp[j].first));
                else
                    if(vp[i].first == vp[j].first && vp[i].second == vp[k].second)
                        ans = max(ans, 1LL * abs(vp[j].second - vp[i].second) * abs(vp[k].first - vp[i].first));
                    else
                        if(vp[i].first == vp[k].first && vp[i].second == vp[j].second)
                            ans = max(ans, 1LL * abs(vp[k].second - vp[i].second) * abs(vp[j].first - vp[i].first));
                        else
                            if(vp[i].first == vp[k].first && vp[k].second == vp[j].second)
                                ans = max(ans, 1LL * abs(vp[k].second - vp[i].second) * abs(vp[j].first - vp[k].first));
                            else
                                if(vp[j].first == vp[k].first && vp[i].second == vp[j].second)
                                    ans = max(ans, 1LL * abs(vp[k].second - vp[j].second) * abs(vp[j].first - vp[i].first));
                                else
                                    if(vp[j].first == vp[k].first && vp[i].second == vp[k].second)
                                        ans = max(ans, 1LL * abs(vp[k].second - vp[j].second) * abs(vp[k].first - vp[i].first));                          
            }

    cout << ans;
    return 0;
}

with open("triangles.in", "r") as fin:
    n = int(fin.readline().strip())
    vp = []
    for _ in range(n):
        a, b = map(int, fin.readline().split())
        vp.append((a, b))
ans = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if vp[i][0] == vp[j][0] and vp[j][1] == vp[k][1]:
                area = abs(vp[j][1] - vp[i][1]) * abs(vp[k][0] - vp[j][0])
                ans = max(ans, area)
            elif vp[i][0] == vp[j][0] and vp[i][1] == vp[k][1]:
                area = abs(vp[j][1] - vp[i][1]) * abs(vp[k][0] - vp[i][0])
                ans = max(ans, area)
            elif vp[i][0] == vp[k][0] and vp[i][1] == vp[j][1]:
                area = abs(vp[k][1] - vp[i][1]) * abs(vp[j][0] - vp[i][0])
                ans = max(ans, area)
            elif vp[i][0] == vp[k][0] and vp[k][1] == vp[j][1]:
                area = abs(vp[k][1] - vp[i][1]) * abs(vp[j][0] - vp[k][0])
                ans = max(ans, area)
            elif vp[j][0] == vp[k][0] and vp[i][1] == vp[j][1]:
                area = abs(vp[k][1] - vp[j][1]) * abs(vp[j][0] - vp[i][0])
                ans = max(ans, area)
            elif vp[j][0] == vp[k][0] and vp[i][1] == vp[k][1]:
                area = abs(vp[k][1] - vp[j][1]) * abs(vp[k][0] - vp[i][0])
                ans = max(ans, area)
with open("triangles.out", "w") as fout:
    fout.write(str(ans))