Problem A
Fractal
Input: Standard Input
Output: Standard Output
Time Limit: 3 Seconds
Below you can see picture of a well-known fractal. Actually this picture shows the steps of the making of a fractal:
In this problem you will have to draw a fractal very
similar to the one above. The fractal that you have to work with is given
below:
In real life it is impossible to draw a fractal exactly according to
its definition because somewhere we must stop drawing it. For example in the
picture above we have stopped drawing when the length of the line on which a
triangle has to be drawn is less than five.
Now let us discuss in detail how the fractal is to be drawn. You will
be given the coordinates of A (x1,
y1) and B
(x2, y2). In the figure above the coordinate of A is (-300, -100) and the coordinate of B is (300, -200). C and D are the points, which divides AB in ratio 1:3 and 3:1. So now you have to draw an equilateral triangle CED based on CD, of course the base is erased. And then you find two
points, which divide CE in the ratio 1:3 and 3:1. The same thing applies for ED and this process continues recursively up to the point
when the length of the side of drawn equilateral triangles is less than a
certain value T. Now if you look at the picture above you will find that
it has two terminal points A and B and many corner points like C, E and D. Your job is to find the coordinates of these terminal
points and corner points and print them in a certain order.
Input
The input file contains less than 10
lines of input.
Each line contains five numbers. The first
four numbers are the coordinates x1,y1, x2,
y2 (-10000<x1,y1,x2,y2<10000)
and the last number T(1<T<1000) is the terminating threshold
value. I mean when the line to be drawn will be less than T drawing will
stop. The value of T will be such that the length of the line to be
drawn will never be equal to T.
Input is terminated by a case whose value of T
is less than 1. This case should not be processed.
Output
For each line of
input you should output S+2 lines of outputs. The first line is the
serial no of the output as shown in the sample output. Next line contains the
number S, where S is the number of vertex and terminal points
in the drawn fractal. Each of the S lines after that contains two floating-point
numbers indicating the coordinate of one terminal point or vertex. The terminal
points should be sorted in increasing order of the value of abscissa of the
coordinate. In case of a tie the points should be sorted in ascending order of
the ordinate. Two values are considered same if they differ by a value less
than 1e-8. All printed floating point numbers have five digits after the decimal
point. Errors less than 2*10-5 will be tolerated.
Sample Input Output for Sample
Input
10 10 -10 -10 5.1-10 -10 10 10 5.15 5 -5 -8 .3 |
Case
1: 11 -10.00000
-10.00000 -5.00000
-5.00000 -1.58494
-5.91506 0.24519
-12.74519 5.00000
5.00000 5.24519
-7.74519 5.91506
1.58494 7.74519
-5.24519 8.66025
-8.66025 10.00000
10.00000 12.74519
-0.24519 Case
2: 11 -12.74519
0.24519 -10.00000
-10.00000 -8.66025
8.66025 -7.74519
5.24519 -5.91506
-1.58494 -5.24519
7.74519 -5.00000
-5.00000 -0.24519
12.74519 1.58494
5.91506 5.00000
5.00000 10.00000
10.00000 |
Problemsetter: Shahriar Manzoor, Member of Elite Problemsetters' Panel