Square Pasture
브론즈 III의견: 0
Farmer John has decided to update his farm to simplify its geometry.
Previously, his cows grazed in two rectangular fenced-in pastures. Farmer John
would like to replace these with a single square fenced-in pasture of minimum
size that still covers all the regions of his farm that were previously enclosed
by the former two fences.
Please help Farmer John figure out the minimum area he needs to make his new
square pasture so that if he places it appropriately, it can still cover all the
area formerly covered by the two older rectangular pastures. The square
pasture should have its sides parallel to the x and y axes.
Problem credits: Brian Dean
Problem credits: Brian Dean
The first line in the input file specifies one of the original rectangular
pastures with four space-separated integers \(x_1\) \(y_1\) \(x_2\) \(y_2\), each in
the range \(0 \ldots 10\). The lower-left corner of the pasture is at the point
\((x_1, y_1)\), and the upper-right corner is at the point \((x_2, y_2)\), where
\(x_2 > x_1\) and \(y_2 > y_1\).
The second line of input has the same 4-integer format as the first line, and
specifies the second original rectangular pasture. This pasture will not
overlap or touch the first pasture.
The output should consist of one line containing the minimum area required of a
square pasture that would cover all the regions originally enclosed by the two
rectangular pastures.
square.insquare.out6 6 8 8
1 8 4 949In the example above, the first original rectangle has corners \((6,6)\) and
\((8,8)\). The second has corners at \((1,8)\) and \((4,9)\). By drawing a square fence
of side length 7 with corners \((1,6)\) and \((8,13)\), the original areas can still be enclosed; moreover, this is the best possible, since it is impossible to enclose the original areas with a square of side length only 6. Note that there are several different possible valid placements for the square of side length 7, as it could have been shifted vertically a bit.
riseoj 작성
출처 올림피아드 > USACO > 2016-2017 > December > Bronze
평가 및 의견
Square Pasture
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Square Pasture