USACO Bronze 2020 February - Triangles

Author: Mrinall Umasudhan

Appears In

Official Analysis (C++)

Implementation

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 all in O(N3)\mathcal{O}(N^3) time.

Java

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


public class triangles{
  
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(new File("triangles.in"));
		PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("triangles.out")));
		int N = sc.nextInt(); 
		int[][] vertices = new int[N][2]; // Store the vertices in a 2D array

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