레이팅 미적용농부 존은 농장의 기하학적 구조를 단순화하기 위해 농장을 새로 정비하기로 했다. 이전에는 소들이 울타리로 둘러싸인 두 개의 직사각형 목초지에서 풀을 뜯었다. 농부 존은 이 두 목초지를, 기존의 두 울타리가 둘러싸던 농장의 모든 영역을 여전히 덮는 최소 크기의 정사각형 목초지 하나로 교체하려고 한다.
새 정사각형 목초지를 적절히 배치했을 때 기존의 두 직사각형 목초지가 덮던 모든 영역을 여전히 덮을 수 있도록 하기 위해 필요한 최소 넓이를 구해 농부 존을 도와주자. 정사각형 목초지의 변은 x축과 y축에 평행해야 한다.
문제 출제: 브라이언 딘(Brian Dean)
문제 출제: 브라이언 딘(Brian Dean)
입력의 첫째 줄에 기존 직사각형 목초지 중 하나가 공백으로 구분된 네 정수 \(x_1\) \(y_1\) \(x_2\) \(y_2\)로 주어지며, 각각은 \(0 \ldots 10\) 범위에 있다. 목초지의 왼쪽 아래 꼭짓점은 \((x_1, y_1)\)이고 오른쪽 위 꼭짓점은 \((x_2, y_2)\)이며, \(x_2 > x_1\)이고 \(y_2 > y_1\)이다.
입력의 둘째 줄에는 첫째 줄과 같은 네 정수 형식으로 두 번째 기존 직사각형 목초지가 주어진다. 이 목초지는 첫 번째 목초지와 겹치거나 닿지 않는다.
기존의 두 직사각형 목초지가 둘러싸던 모든 영역을 덮을 수 있는 정사각형 목초지의 최소 넓이를 한 줄에 출력한다.
square.in · 출력을 쓸 파일 square.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