[UVA] 10609 - Fractal
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 #include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
const double sqrt3 = sqrt(3);
vector< pair<double, double> > ret;
void dfs(double ax, double ay, double bx, double by, double T) {
double len = hypot(ax - bx, ay - by);
double vx, vy, cx, cy, dx, dy, ex, ey;
if(len/2 < T) return ;
vx = bx - ax, vy = by - ay;
cx = ax + vx/4.0, cy = ay + vy/4.0;
dx = ax + 3*vx/4.0, dy = ay + 3*vy/4.0;
ex = (ax + bx)/2 + sqrt3/4 * vy;
ey = (ay + by)/2 - sqrt3/4 * vx;
ret.push_back(make_pair(cx, cy));
dfs(cx, cy, ex, ey, T);
ret.push_back(make_pair(ex, ey));
dfs(ex, ey, dx, dy, T);
ret.push_back(make_pair(dx, dy));
}
bool cmp(pair<double, double> a, pair<double, double> b) {
if(fabs(a.first - b.first) < 1e-6)
return a.second < b.second;
return a.first < b.first;
}
int main() {
double ax, ay, bx, by, T;
int cases = 0;
while(scanf("%lf %lf %lf %lf %lf", &ax, &ay, &bx, &by, &T) == 5 && T >= 1) {
ret.clear();
dfs(bx, by, ax, ay, T);
printf("Case %d:\n", ++cases);
ret.push_back(make_pair(ax, ay));
ret.push_back(make_pair(bx, by));
sort(ret.begin(), ret.end(), cmp);
printf("%d\n", ret.size());
for(int i = 0; i < ret.size(); i++)
printf("%.5lf %.5lf\n", ret[i].first, ret[i].second);
}
return 0;
}