50148. Stack Rectangles, Again

I'm a slow walker, but I never walk backwards.

Task Description

There are $n$ rectangles with given width and length. The task is to choose and stack the maximum number of them.

One rectangle A can only stack on the top of another rectangle B if A has a larger index than B, and A can fit on top of B, which may be one of the following two cases. Note that a rectangle can be rotated by 90 degrees.

  • When this program is compiled with flag LARGEONSMALL, A can fit on top of B means that rectangle $B$ is fully covered by rectangle $A$.
  • When this program is compiled with flag SMALLONLARGE, A can fit on top of B means that rectangle $A$ is fully covered by rectangle $B$.

There could be multiple sets of rectangles with the same maximum number of rectangles that can be stacked together. In that case we will report only one set according to the following rules.

  • When the compilation flag MAXAREASUM is defined, we will report the set with the maximum sum of area of these rectangles.
  • When the compilation flag MINAREASUM is defined, we will report the set with the minimum sum of area instead.

Input Format

The input only has one test case. The first line is the number of rectangles $n$. The following $n$ lines are the width $w$ and length $l$ for each rectangle.

  • $0 \lt n \leq 100$
  • $0 \lt w, l \leq 100$

Output Format

The output has two integers, which are the maximum number of rectangles we can stack and the maximum (or minimal) sum of area according to the compilation flag. Note that we have four combinations, so there are four subtasks.

Subtasks

  • 25 points: The program is compiled with flag LARGEONSMALL and MAXAREASUM. gcc main.c -std=c99 -O2 -DLARGEONSMALL -DMAXAREASUM
  • 25 points: The program is compiled with flag SMALLONLARGE and MAXAREASUM. gcc main.c -std=c99 -O2 -DSMALLONLARGE -DMAXAREASUM
  • 25 points: The program is compiled with flag LARGEONSMALL and MINAREASUM. gcc main.c -std=c99 -O2 -DLARGEONSMALL -DMINAREASUM
  • 25 points: The program is compiled with flag SMALLONLARGE and MINAREASUM. gcc main.c -std=c99 -O2 -DSMALLONLARGE -DMINAREASUM

Sample Input 1

4
4 4
3 3
1 1
2 2

Sample Output 1 (with flag LARGEONSMALL and MAXAREASUM)

2 5

Sample Input 2

4
4 4
3 3
1 1
2 2

Sample Output 2 (with flag SMALLONLARGE and MAXAREASUM)

3 29

Sample Input 3

4
4 4
3 3
1 1
2 2

Sample Output 3 (with flag LARGEONSMALL and MINAREASUM)

2 5

Sample Input 4

4
4 4
3 3
1 1
2 2

Sample Output 4 (with flag SMALLONLARGE and MINAREASUM)

3 26

Discussion