USACO 2020 February Contest, Bronze Problem 1. Triangles

USACO 2020 February Contest, Bronze Problem 1. Triangles

Farmer John would like to create a triangular pasture for his cows.

There are?NN?fence posts (3≤N≤1003≤N≤100) at distinct points?(X1,Y1)…(XN,YN)(X1,Y1)…(XN,YN)?on the 2D map of his farm. He can choose three of them to form the vertices of the triangular pasture as long as one of the sides of the triangle is parallel to the?xx-axis and another side is parallel to the?yy-axis.

What is the maximum area of a pasture that Farmer John can form? It is guaranteed that at least one valid triangular pasture exists.

 

 

 

SAMPLE INPUT:

4
0 0
0 1
1 0
1 2

SAMPLE OUTPUT:

2

Posts at?(0,0)(0,0),?(1,0)(1,0), and?(1,2)(1,2)?form a triangle of area?11. Thus, the answer is?2?1=22?1=2. There is only one other triangle, with area?0.50.5.

 

Problem credits: Travis Hance

?USACO 2020 February Contest, Bronze Problem 1. Triangles 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Jonathan Paulson)

This problem can be solved by brute force. We can try every triple of fence posts to see if they form a valid pasture and take the biggest. There are only?100100?posts, so there are only?10031003?- a million - triples to try. This is well within time limits (if there were over?100100?million triples to try, that would be worrying).

How do we try a triple? For a triple to be valid, one post must be the corner, another must be directly to the left or right of the corner (i.e. have the same y-coordinate as the corner), and the last must be directly up or down from the corner (i.e. have the same?xx-coordinate).

Assuming the triple forms a valid triangle, how do we find the area? That's just one-half times base times height. The base is just the difference in?xx-coordinates between the corner and second post, and the height is the difference in?yy-coordinates between the corner and third post.

So the final solution is to try all triples, and among the valid ones take the biggest area.

Implementation tips:

 

1. You are supposed to output twice the maximum area, not the area. The easiest way to do this is to ignore the one-half in the area formula (rather than doing it at the end).
2. It's easier to iterate through the triples in all possible orders. That way you can use the order by assuming the first post is the corner, the second post forms the base, and the last post forms the height. If you were supposed to jumble them up, some other triple will catch that case.

C++ code:

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
  freopen("triangles.in", "r", stdin);
  freopen("triangles.out", "w", stdout);
  ll n;
  cin >> n;
  vector<ll> X(n, 0);
  vector<ll> Y(n, 0);
  for(ll i=0; i<n; i++) {
    cin >> X[i] >> Y[i];
  }
  // i will be corner
  // j will be flat (same x-coordinate as i)
  // k will be same y-coordinate as i
  ll best = -1;
  for(ll i=0; i<n; i++) {
    for(ll j=0; j<n; j++) {
      for(ll k=0; k<n; k++) {
        if(Y[i]==Y[j] && X[i]==X[k]) {
          ll area = (X[j]-X[i]) * (Y[k]-Y[i]);
          if(area < 0) { area *= -1; }
          if(area > best) {
            best = area;
          }
        }
      }
    }
  }
  cout << best << endl;
}

Java code (from Nick Wu):

import java.io.*;
import java.util.*;
public class Solution {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new FileReader("triangles.in"));
    PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("triangles.out")));
    int n = Integer.parseInt(br.readLine());
    int[] x = new int[n];
    int[] y = new int[n];
    for(int i = 0; i < n; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      x[i] = Integer.parseInt(st.nextToken());
      y[i] = Integer.parseInt(st.nextToken());
    }
    int ret = 0;
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) { // same x-coordinate
        if(i == j || x[i] != x[j]) continue;
        for(int k = 0; k < n; k++) { // same y-coordinate
          if(i == k || y[i] != y[k]) continue;
          ret = Math.max(ret, Math.abs(x[k] - x[i]) * Math.abs(y[j] - y[i]));
        }
      }
    }
    pw.println(ret);
    pw.close();
  }
}

[/hide]