|
Size: 1537
Comment:
|
← Revision 7 as of 2011-01-20 12:12:48 ⇥
Size: 1718
Comment: Mi ha cancellato la pagina
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 7: | Line 7: |
| * Input predicates: area/2, max_square_num/1, square/2 * Output predicates: pos/3 |
|
| Line 15: | Line 11: |
| The input contains a fact area(W,H) which specifies the dimension of the rectangular area (the top edge is W units and the left edge is H units), a fact max_square_num(N) which gives the number of squares to be packed (the squares are numbered from 1 to N), and a fact square(I,Size) for each I between 1 and N which gives the size of the square numbered I. | == Predicates == |
| Line 17: | Line 13: |
| The output should contain a fact pos(I,X,Y) for each square which gives the coordinates of the left upper corner of the square in the rectangular area. Let W be the width and H the height of the rectangular area, and Size be the size of the square. Then the coordinates X and Y must satisfy: | * '''Input''': {{{area/2, max_square_num/1, square/2}}} |
| Line 19: | Line 15: |
| 0 =< X =< W-Size <<BR>> | * '''Output''': {{{pos/3}}} == Input format == The input contains a fact {{{area(W,H)}}} which specifies the dimension of the rectangular area (the top edge is W units and the left edge is H units), a fact {{{max_square_num(N)}}} which gives the number of squares to be packed (the squares are numbered from 1 to N), and a fact {{{square(I,Size)}}} for each I between 1 and N which gives the size of the square numbered I. == Output format == The output should contain a fact {{{pos(I,X,Y)}}} for each square which gives the coordinates of the left upper corner of the square in the rectangular area. Let W be the width and H the height of the rectangular area, and Size be the size of the square. Then the coordinates X and Y must satisfy: {{{ 0 =< X =< W-Size |
| Line 21: | Line 27: |
| }}} | |
| Line 22: | Line 29: |
| Example: For the following input | == Example(s) == |
| Line 24: | Line 31: |
| area(6,4). <<BR>> max_square_num(3). <<BR>> square(1,4). <<BR>> square(2,2). <<BR>> square(3,2). <<BR>> |
For the following input {{{ area(6,4). max_square_num(3). square(1,4). square(2,2). square(3,2). }}} one possible solution is: {{{ pos(1,0,0). pos(2,4,0). pos(3,4,2). }}} |
| Line 30: | Line 46: |
| one possible solution is: pos(1,0,0). <<BR>> pos(2,4,0). <<BR>> pos(3,4,2). <<BR>> |
== Author(s) == * Author: Neng-Fa Zhou * Affiliation: CUNY Brooklyn College and Graduate Center, USA |
Packing
Problem Description
Given a rectangular area of a known dimension and a set of squares, each of which has a known dimension, the problem is to pack all the squares into the rectangular area such that no two squares overlap each other. There can be wasted spaces in the rectangular area.
The rectangular area forms a coordinate plane where the left upper corner of the area is the origin, the top edge is the x-axis, and the left edge is the y-axis.
Predicates
Input: area/2, max_square_num/1, square/2
Output: pos/3
Input format
The input contains a fact area(W,H) which specifies the dimension of the rectangular area (the top edge is W units and the left edge is H units), a fact max_square_num(N) which gives the number of squares to be packed (the squares are numbered from 1 to N), and a fact square(I,Size) for each I between 1 and N which gives the size of the square numbered I.
Output format
The output should contain a fact pos(I,X,Y) for each square which gives the coordinates of the left upper corner of the square in the rectangular area. Let W be the width and H the height of the rectangular area, and Size be the size of the square. Then the coordinates X and Y must satisfy:
0 =< X =< W-Size
0 =< Y =< H-Size
Example(s)
For the following input
area(6,4). max_square_num(3). square(1,4). square(2,2). square(3,2).
one possible solution is:
pos(1,0,0). pos(2,4,0). pos(3,4,2).
Author(s)
- Author: Neng-Fa Zhou
- Affiliation: CUNY Brooklyn College and Graduate Center, USA