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 $100$ posts, so there are only $100^3$ - a million - triples to try. This is well within time limits (if there were over $100$ 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 $x$-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 $x$-coordinates between the corner and second post, and the height is the difference in $y$-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:
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(); } }