Output

IME 04-10859 - DESENV. E IMPLEMENTAÇÃO DE ALGORITMOS – 07/06/2014
Este caderno contém 13 páginas com a descrição de 10 problemas definidos a seguir:
A – The Skyline Problem (Valladolid 105)
B – Pipe (Valladolid 303)
C – Convex Hull Finding (Valladolid 681)
D – Boundary Poinats (Valladolid 1206)
E – Chainsaw Massacre (Valladolid 10043)
F – Useless Tile Packers (Valladolid 10065)
G – The Closest Pair Problem (Valladolid 10245)
H – The Great Divide (Valladolid 10256)
I – Beautiful Points (Valladolid 10750)
J – Convex Hull (Valladolid 11626)
Desafios:
K – Trash Removal (Valladolid 1111)
L – Smallest Bounding Rectangle (Valladolid 10173)
M – Sultan and Khairun Shundori(Valladolid 11612)
N – Stick Makes Gold (Valladolid 11653)
1
Problema A (Valladolid 105)
The Skyline Problem
Background
With the advent of high speed graphics workstations, CAD (computer-aided design) and other
areas (CAM, VLSI design) have made increasingly effective use of computers. One of the
problems with drawing images is the elimination of hidden lines -- lines obscured by other parts
of a drawing.
The Problem
You are to design a program to assist an architect in drawing the skyline of a city given the
locations of the buildings in the city. To make the problem tractable, all buildings are
rectangular in shape and they share a common bottom (the city they are built in is very flat). The
city is also viewed as two-dimensional. A building is specified by an ordered triple (Li, Hi, Ri)
where Li and are left and right coordinates, respectively, of building i and Hi is the height of
the building. In the diagram below buildings are shown on the left with triples
(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)
the skyline, shown on the right, is represented by the sequence:
(1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0)
The Input
The input is a sequence of building triples. All coordinates of buildings are positive integers less
than 10,000 and there will be at least one and at most 5,000 buildings in the input file. Each
building triple is on a line by itself in the input file. All integers in a triple are separated by one
or more spaces. The triples will be sorted by Li, the left x-coordinate of the building, so the
building with the smallest left x-coordinate is first in the input file.
The Output
The output should consist of the vector that describes the skyline as shown in the example
above. In the skyline vector(v1,v2,v3,…vn-2,vn-1,vn), the such that i is an even number represent
a horizontal line (height). The vi such that i is an odd number represent a vertical line
(x-coordinate). The skyline vector should represent the ``path'' taken, for example, by a bug
starting at the minimum x-coordinate and traveling horizontally and vertically over all the lines
that define the skyline. Thus the last entry in the skyline vector will be a 0. The coordinates
must be separated by a blank space.
Sample Input
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28
Sample Output
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
2
Problema B (Valladolid 303)
Pipe
The GX Light Pipeline Company started to prepare bent pipes for the new transgalactic light
pipeline. During the design phase of the new pipe shape the company ran into the problem of
determining how far the light can reach inside each component of the pipe. Note that the material
which the pipe is made from is not transparent and not light reflecting.
Each pipe component consists of many straight pipes connected tightly together. For the
programming purposes, the company developed the description of each component as a sequence of
points [x1,y1],[x2,y2],...[xn,yn] , where x1 < x2 <...<xn. These are the upper points of the pipe contour.
The bottom points of the pipe contour consist of points with y-coordinate decreased by 1. To each
upper point [xi,yi] there is a corresponding bottom point [xi,yi-1] (see picture above). The company
wants to find, for each pipe component, the point with maximal x-coordinate that the light will
reach. The light is emitted by a segment source with endpoints [x1,y1-1] and [x1,y1] (endpoints are
emitting light too). Assume that the light is not bent at the pipe bent points and the bent points do
not stop the light beam.
Input
The input file contains several blocks each describing one pipe component. Each block starts with
the number of bent points 2 ≤ n ≤ 20 on separate line. Each of the next n lines contains a pair of
real values xi,yi separated by space. The last block is denoted with n = 0.
Output
The output file contains lines corresponding to blocks in input file. To each block in the input file
there is one line in the output file. Each such line contains either a real value, written with precision
of two decimal places, or the message Through all the pipe.. The real value is the desired
maximal x-coordinate of the point where the light can reach from the source for corresponding
pipe component. If this value equals to
appear in the output file.
, then the message Through all the pipe. will
Sample Input
17 -16.55
0
4
0 1
2 2
4 1
6 4
6
0 1
2 -0.6
5 -4.45
7 -5.57
12 -10.8
Sample Output
4.67
Through all the pipe.
3
Problema C (Valladolid 681)
Convex Hull Finding
Given a single connected contour, which is either convex or non-convex (concave), use any
algorithm to find its Convex Hull, i.e., the smallest convex contour enclosing the given shape.
If the given contour is convex, then its convex hull is the original contour itself. The maximal
size of the shape is 512 x 512, and the maximal number of the vertices of the shape is 512.
Write a program to read the input data (the given shapes) from a disk file, implement your
convex hull finding algorithm, and then output the shape data of the results to the standard
output.
Input
The order of the vertices is counterclockwise in X-Y Cartesian Plane (if you consider the origin
of the display window is on the upper-left corner, then the orientation of the vertices is
clockwise), and none of the neighboring vertices are co-linear. Since all the shapes are closed
contours, therefore, the last vertex should be identical to the first vertex. There are several sets
of data within a given data file. The negative number -1 is used to separate the data set.
Line
Data in
Number the File
Explanation
1
K
a positive integer showing how many sets of data in this file
2
N
a positive integer showing the number of vertices for the shape
3
two positive integers for the first vertex (X1, Y1)
4
two positive integers for the next neighboring vertex (X2, Y2)
...
two positive integers for the last vertex (XN, YN)
N+2
N+3
-1
Delimiter
N+4
M
a positive integer showing the number of vertices for the next shape
N+5
two positive integers for the first vertex
...
Note: Please note that the Line Number, Data in the File and Explanation are not given in the
file. They are shown here only to assist you in reading the data.
Output
Output the convex hull of all K input shapes to the standard output. The data format should be
the same as the input file. In addition, the vertex with the smallest Y value should be the first
point and if there are points with the same Y value, then the smallest X value within those points
should be the first point.
4
Sample Input
Sample Output
3
15
30 30
50 60
60 20
70 45
86 39
112 60
200 113
250 50
300 200
130 240
76 150
47 76
36 40
33 35
30 30
-1
12
50 60
60 20
70 45
100 70
125 90
200 113
250 140
180 170
105 140
79 140
60 85
50 60
-1
6
60 20
250 140
180 170
79 140
50 60
60 20
3
8
60 20
250 50
300 200
130 240
76 150
47 76
30 30
60 20
-1
6
60 20
250 140
180 170
79 140
50 60
60 20
-1
6
60 20
250 140
180 170
79 140
50 60
60 20
5
Problema D (Valladolid 1206)
Boundary Points
The convex hull of a set of points Q on a plane is the smallest convex polygon P for
which each point in Q is in the boundary or inside P .
``The problem of finding convex hulls finds its practical applications in pattern
recognition, image processing, statistics and geographic information systems or GIS. It
also serves as a tool, a building block for a number of other computational-geometric
algorithms. For example, consider the problem of finding the diameter of a set of points,
which is the pair of points a maximum distance apart. The diameter will always be the
distance between two points on the convex hull.
For planar objects, i.e., lying in the plane, the convex hull may be easily visualized by
imagining an elastic band stretched open to encompass the given objects; when
released, it will assume the shape of the required convex hull. It may seem natural to
generalise this picture to higher dimensions by imagining the objects enveloped in a sort
of idealized unpressurized elastic membrane or balloon under tension. However, the
equilibrium (minimum-energy) surface in this case may not be the convex hull-parts of
the resulting surface may have negative curvature, like a saddle surface. For the case of
points in 3-dimensional space, if a rigid wire is first placed between each pair of points,
then the balloon will spring back under tension to take the form of the convex hull of
the points." (from Wikipedia)
Write a program that outputs the convex polygon P for a set of points Q.
Input
The set of points in Q are given in one line and the program should be able to read any
number of lines where each line is one set of points in Q. Each point is of the format (x,
y) where x, y
R.
Output
Each test case will be displayed in one line of output. The first point and the last point
of the convex hull must match. Any sequence of points defining the convex hull will be
considered valid.
Sample Input
(-2,1) (-1,-2) (-1,1) (-1,2) (-1,3) (0,0) (1,-1) (1,1) (2,-2) (2,1)
(3,2)
Sample Output
(-1,-2) (2,-2) (3,2) (-1,3) (-2, 1) (-1,-2)
6
Problema E (Valladolid 10043)
Chainsaw Massacre
Background
As every year the Canadian Lumberjack Society has just held its annual woodcutting
competition and the national forests between Montreal and Vancouver are devastated.
Now for the social part! In order to lay out an adequate dance floor for the evening party
the organizing committee is looking for a large rectangular area without trees. Naturally,
all lumberjacks are already drunk and nobody wants to take the risk of having any of
them operate a chainsaw.
The Problem
The organizing committee has asked you to find the largest yet free rectangle which
could serve as the dance floor. The area in which you should search is also rectangular
and the dance floor must be entirely located in that area. Its sides should be parallel to
the borders of the area. It is allowed that the dance floor is located at the borders of the
area and also that trees grow on the borders of the dance floor. What is the maximum
size of the dance floor?
The Input
The first line of the input specifies the number of scenarios. For each scenario, the first
line provides the length l and width w of the area in meters ( 0 < l, w ≤ 10000 , both
integers). Each of the following lines describes either a single tree, or a line of trees
according to one of the following formats:
• 1 x y, where the ``one'' characterizes a single tree, and x and y provide its
coordinates in meters with respect to the upper left corner.
• k x y dx dy, where k>1 provides the number of trees in a line with coordinates
(x,y),(x+dx,y+dy),...,(x+(k-1)dx,y+(k-1)dy).
• 0 denotes the end of the scenario.
The coordinates x, y, dx, and dy are given as integers. It is guaranteed that all the trees
are situated in the area, i.e. have coordinates in [0,l] x [0,w] . There will be at most
1000 trees.
The Output
For each scenario print a line containing the maximum size of the dance floor measured
in square meters.
Sample Input
2
2 3
0
10 10
2 1 1 8 0
2 1 9 8 0
0
Sample Output
6
80
7
Problema F (Valladolid 10065)
Useless Tile Packers
Yes, as you have apprehended the Useless Tile Packers (UTP) pack tiles. The tiles are
of uniform thickness and have simple polygonal shape. For each tile a container is
custom-built. The floor of the container is a convex polygon and under this constraint it
has the minimum possible space inside to hold the tile it is built for. But this strategy
leads to wasted space inside the container.
The UTP authorities are interested to know the percentage of wasted space for a given tile.
Input
The input file consists of several data blocks. Each data block describes one tile.
The first line of a data block contains an integer N (3 <= N <= 100) indicating
the number of corner points of the tile. Each of the next N lines contains two integers
giving the (x, y) co-ordinates of a corner point (determined using a suitable origin and
orientation of the axes) where 0 <= x, , y <= 1000. Starting from the first point given in
the input the corner points occur in the same order on the boundary of the tile as they
appear in the input. No three consecutive points are co-linear.
The input file terminates with a value of 0 for N.
Output
For each tile in the input output the percentage of wasted space rounded to two digits
after the decimal point. Each output must be on a separate line. Print a blank line after
each output block.
Tile #1
Sample Input
Wasted Space = 25.00 %
5
0 0
Tile #2
2 0
Wasted Space = 0.00 %
2 2
1 1
0 2
5
0 0
0 2
1 3
2 2
2 0
0
Sample Output
8
Problema G (Valladolid 10256)
The Closest Pair Problem
Given a set of points in a two dimensional space, you will have to find the distance
between the closest two points.
Input
The input file contains several sets of input. Each set of input starts with an integer N
(0<=N<=10000), which denotes the number of points in this set. The next N line
contains the coordinates of N two-dimensional points. The first of the two numbers
denotes the X-coordinate and the latter denotes the Y-coordinate. The input is
terminated by a set whose N=0. This set should not be processed. The value of the
coordinates will be less than 40000 and non-negative.
Output
For each set of input produce a single line of output containing a floating point number
(with four digits after the decimal point) which denotes the distance between the closest
two points. If there is no such two points in the input whose distance is less than 10000,
print the line INFINITY.
Sample Input
3
0 0
10000 10000
20000 20000
5
0 2
6 67
43 71
39 107
189 140
0
Sample Output
INFINITY
36.2215
9
Problema H (Valladolid 10256)
The Great Divide
Somewhere in Gaul, there is a little village very like the village where Asterix and
Obelix live. Not very long ago they had only one chief Altruistix and peace reigned in
the village. But now those happy days are just dreams. The villagers are now divided.
Some of the villagers have elected Majestix as their chief and the others have elected
Cleverdix.
Majestix
Cleverdix
The two chiefs have decided to divide the village into two parts by digging a straight
ditch through the middle of the village so that the houses of the supporters of Majestix
lie on one part and those of the followers of Cleverdix lie on the other. So, they have
invited Getafix, the venerable druid of Asterix’s village, to figure out whether such a
dividing line exists or not.
Getafix
Since Getafix knows that you are so good in programming, he seeks your help.
Input
The input may contain multiple test cases.
The first line of each test case contains two integers M and C (1 ≤ M, C ≤ 500),
indicating the number of houses of the supporters of Majestix and Cleverdix
respectively.
Each of the next M lines contains two integers x and y (-1000 ≤ x, y ≤ 1000) giving the
co-ordinates of the house of a supporter of Majestix. For convenience each house is
considered as a single point on the plane.
Each of the next C lines contains two integers x and y (-1000 ≤ x, y ≤ 1000) giving the
co-ordinates of the house of a supporter of Cleverdix.
The input will terminate with two zeros for M and C.
10
Output
For each test case in the input output a line containing either “Yes” or “No” depending
on whether there exists a straight line that divides the two set of houses. The dividing
line can NOT contain points of both sides.
Sample Input
43
100 600
200 400
600 500
300 700
400 100
600 200
500 300
43
100 600
400 100
600 200
500 300
200 400
600 500
300 700
00
Sample Output
Yes
No
11
Problema I (Valladolid 10750)
Beautiful Points
There are several points on the plane named beauty points. Given a point A, its ugliness
is defined as |AB|+|AC|, where B and C are two beauty points nearest to A.
Your task is: given beauty points, find the most beautiful point, i.e., the point having
least ugliness. Note: the most beautiful point doesn't have to be a beauty point.
Input
The first line of the input contains the number of the test cases, which is at most 10. The
descriptions of the test cases follow. The first line of a test case descriptions contains an
integer N (2 ≤ N ≤ 10000), which is the number of beauty points. Each of the next N
lines contains two integers X and Y separated by a space (-10000 ≤ X, Y ≤ 10000)
being the coordinates of a beauty point. No two beauty points in a test case description
have the same coordinates. The test cases are separated by blank lines.
Output
For each test case in the input, output the coordinates of any most beautiful point
separated by a space, with at least three digits after the decimal point. Print a blank line
between test cases.
Exemples of Input
2
4
0
0
1
1
0
1
1
0
4
-1 -1
0 0
1 0
2 1
Output for exemples
0.500 0.000
0.500 0.000
12
Problema J (Valladolid 11626)
Convex Hull
Finding the convex hull of a set of points is an important problem that is often part of a
larger problem. There are many algorithms for finding the convex hull. Since problems
involving the convex hull sometimes appear in the ACM World Finals, it is a good idea
for contestants to know some of these algorithms.
Finding the convex hull of a set of points in the plane can be divided into two sub-tasks.
First, given a set of points, find a subset of those points that, when joined with line
segments, form a convex polygon that encloses all of the original points. Second, output
the points of the convex hull in order, walking counter-clockwise around the polygon.
In this problem, the first sub-task has already been done for you, and your program
should complete the second sub-task. That is, given the points that are known to lie on
the convex hull, output them in order walking counter-clockwise around the hull.
Input
The first line of input contains a single integer, the number of test cases to follow. The
first line of each test case contains a single integer 3 <= n<= 100000, the number of
points. The following n lines of the test case each describe a point. Each of these lines
contains two integers and either a Y or an N, separated by spaces. The two integers
specify the x- and y-coordinates of the point. A Y indicates that the point is on the
convex hull of all the points, and a N indicates that it is not. The x- and y-coordinates of
each point will be no less than -1000000000 and no greater than 1000000000. No point
will appear more than once in the same test case. The points in a test case will never all
lie on a line.
Output
For each test case, generate the following output. First, output a line containing a single
integer m, the number of points on the convex hull. Next output m lines, each
describing a point on the convex hull, in counter-clockwise order around the hull. Each
of these lines should contain the x-coordinate of the point, followed by a space,
followed by the y-coordinate of the point. Start with the point on the hull whose xcoordinate is minimal. If there are multiple such points, start with the one whose ycoordinate is minimal.
-1 1 Y
Sample Input
1
5
11Y
1 -1 Y
00N
-1 -1 Y
Sample Output
4
-1 -1
1 -1
11
-1 1
13

Download Report