USACO Bronze 2020 February - Triangles

Authors: Ryan Chou, Mrinall Umasudhan, Sathvik Chundru

Edit This Page

Table of Contents

ExplanationImplementation

Official Analysis (C++)

Explanation

Brute force all possible right triangles by looping over all triples of points and checking whether they form a right triangle. If so, compute the area and find the maximum over all right triangles.

Implementation

Time Complexity: O(N3)\mathcal{O}(N^3)

C++

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


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


	int n;
	cin >> n;
	vector<int> x(n);  // x coordinates of all fence posts
	vector<int> y(n);  // y coordinates of all fence posts

Java

import java.io.*;
import java.util.*;


public class Triangles {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("triangles.in"));


		int n = Integer.parseInt(read.readLine());
		int[] x = new int[n];  // x coordinates of all fence posts
		int[] y = new int[n];  // y coordinates of all fence posts

Python

with open("triangles.in") as read:
	n = int(read.readline())
	x = []  # x coordinates of all fence posts
	y = []  # y coordinates of all fence posts
	for _ in range(n):
		x_i, y_i = [int(i) for i in read.readline().split()]
		x.append(x_i)
		y.append(y_i)


max_area = 0

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum