USACO Bronze 2016 December - Square Pasture

Authors: Maggie Liu, Dong Liu

Edit This Page

Official Analysis (Java)

Video Solution

By Maggie Liu

Video Solution Code

Explanation

We can first find the smallest rectangle that covers both pastures. This rectangle will need to cover the smaller of the left sides of both pastures and the larger of the right sides of both pastures. It will also need to cover the smaller of the bottom sides and the larger of the top sides of both pastures. The smallest square has a side length equal to the longer side length of the rectangle.

Implementation

Time Complexity: O(1)\mathcal{O}(1)

C++

#include <cstdio>
#include <iostream>
using namespace std;


int main() {
	freopen("square.in", "r", stdin);
	freopen("square.out", "w", stdout);
	int x1, y1, x2, y2;
	int x3, y3, x4, y4;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

Java

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


public class Square {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("square");
		int x1 = io.nextInt(), y1 = io.nextInt();
		int x2 = io.nextInt(), y2 = io.nextInt();
		int x3 = io.nextInt(), y3 = io.nextInt();
		int x4 = io.nextInt(), y4 = io.nextInt();

Python

import sys


sys.stdin = open("square.in", "r")
sys.stdout = open("square.out", "w")


x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())


# find the sides of the smallest rectangle covering both pastures
left = min(x1, x3)

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