主頁 > USACO > Section 1.4 Problem 1

Section 1.4 Problem 1

Packing Rectangles

——————————————————–
IOI 95
The six basic layouts of four rectangles

Four rectangles are given. Find the smallest enclosing (new) rectangle into which these four may be fitted without overlapping. By smallest rectangle, we mean the one with the smallest area.

All four rectangles should have their sides parallel to the corresponding sides of the enclosing rectangle. Figure 1 shows six ways to fit four rectangles together. These six are the only possible basic layouts, since any other layout can be obtained from a basic layout by rotation or reflection. Rectangles may be rotated 90 degrees during packing.

There may exist several different enclosing rectangles fulfilling the requirements, all with the same area. You must produce all such enclosing rectangles.

——————————————————–

PROGRAM NAME: packrec

——————————————————–

INPUT FORMAT

Four lines, each containing two positive space-separated integers that represent the lengths of a rectangle’s two sides. Each side of a rectangle is at least 1 and at most 50.

——————————————————–

SAMPLE INPUT (file packrec.in)

1 2
2 3
3 4
4 5

——————————————————–

OUTPUT FORMAT

The output file contains one line more than the number of solutions. The first line contains a single integer: the minimum area of the enclosing rectangles. Each of the following lines contains one solution described by two numbers p and q with p<=q. These lines must be sorted in ascending order of p, and must all be different.

——————————————————–

SAMPLE OUTPUT (file packrec.out)

40
4 10
5 8

////////////////////////////////////////////////////////

我的答案

http://nopaste.csie.org/e93c0

////////////////////////////////////////////////////////

自我檢討

這題想了很久很久

還是寫出一個超醜的程式碼

用的方法不是題目上暗示的

這裡面

用了三種不同的演算法

前兩種演算法相互重疊

會重複檢查相同的圖形

第三種則是檢查"特例"

雖然通過檢查

但是基本上是失敗的

我想

最大的原因是

我一開始真的想太多了

廣告
分類:USACO 標籤:
  1. 仍無迴響。
  1. No trackbacks yet.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

%d 位部落客按了讚: