1.

/**
* ACM Training 2009
* ACM Problem #10609 - Fractal
* Link: http://uva.onlinejudge.org/external/106/10609.html
*
* @author Felix Dietrich
* @version 1.0, 01/20/2010
*
* Methode: Matrix transformation, Fractals Bruteforce, StringBuffer, TreeSets
* Status : Accepted
* Runtime: 0.036
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.TreeSet;

public class Main
{
public static Point nullPoint = new Point(0, 0);
public static Point firstPoint;
public static Point lastPoint;
public static Point terminalPoint1;
public static Point terminalPoint2;
public static double baseformLength;
public static Point tempP;

/**
* 3x3 matrix class to transform points
*/
public static class Matrix
{
double[][] components;

/**
* Initializes the matrix with the identity matrix.
*/
public Matrix()
{
int rows = 3;
int cols = 3;
components = new double[rows][cols];
// create identity matrix
for (int i = 0; i < rows; i++)
for (int k = 0; k < rows; k++)
if (i != k)
components[i][k] = 0.0;
else
components[i][k] = 1.0;
}

/**
* scales this matrix by the given factor.
*
* @param f
* factor
*/
public void scale(double f)
{
Matrix m = new Matrix();
m.components[0][0] = f;
m.components[1][1] = f;

this.mult(m);
}

/**
* rotates the matrix by the given angle.
*
* @param phi
* angle
*/
public void rotate(double phi)
{
Matrix m = new Matrix();
m.components[0][0] = Math.cos(phi);
m.components[0][1] = -Math.sin(phi);
m.components[1][0] = Math.sin(phi);
m.components[1][1] = Math.cos(phi);

this.mult(m);
}

/**
* moves the matrix by the given deltas. note that the z coordinate
* cannot be given because the matrix is used for 2dim vectors.
*
* @param dx
* @param dy
*/
public void move(double dx, double dy)
{
Matrix m = new Matrix();
m.components[0][2] = dx;
m.components[1][2] = dy;

this.mult(m);
}

/**
* multiplies a matrix with the current and stores the result in this
* matrix.
*
* @param matrix
* to be multiplied to the right side of this matrix.
*/
public void mult(Matrix matrix)
{
Matrix result = new Matrix();
result.components[0][0] = 0;
for (int k = 0; k < 3; k++)
result.components[0][0] += components[0][k]
* matrix.components[k][0];
result.components[0][1] = 0;
for (int k = 0; k < 3; k++)
result.components[0][1] += components[0][k]
* matrix.components[k][1];
result.components[0][2] = 0;
for (int k = 0; k < 3; k++)
result.components[0][2] += components[0][k]
* matrix.components[k][2];
result.components[1][0] = 0;
for (int k = 0; k < 3; k++)
result.components[1][0] += components[1][k]
* matrix.components[k][0];
result.components[1][1] = 0;
for (int k = 0; k < 3; k++)
result.components[1][1] += components[1][k]
* matrix.components[k][1];
result.components[1][2] = 0;
for (int k = 0; k < 3; k++)
result.components[1][2] += components[1][k]
* matrix.components[k][2];
result.components[2][0] = 0;
for (int k = 0; k < 3; k++)
result.components[2][0] += components[2][k]
* matrix.components[k][0];
result.components[2][1] = 0;
for (int k = 0; k < 3; k++)
result.components[2][1] += components[2][k]
* matrix.components[k][1];
result.components[2][2] = 0;
for (int k = 0; k < 3; k++)
result.components[2][2] += components[2][k]
* matrix.components[k][2];
this.components = result.components;
}

/**
* multiplies this matrix with the given vector p and stores the result
* in p. the point p is a 2dim vector, the matrix 3x3. this means that p
* is extended to 3 dimensions, multiplied and then projected on 2
* dimensions by cutting off the 3rd.
*
* @param p
* point to multiply this matrix with
*/
public Point mult(Point p)
{
double x = p.x * components[0][0] + p.y * components[0][1]
+ components[0][2];
double y = p.x * components[1][0] + p.y * components[1][1]
+ components[1][2];
p.x = x;
p.y = y;
return p;
}

/**
* prints the matrix.
*/
public String toString()
{
StringBuffer sb = new StringBuffer();
for (int lrows = 0; lrows < 3; lrows++)
{
for (int lcols = 0; lcols < 3; lcols++)
{
sb.append(components[lrows][lcols]);
sb.append(" ");
}
sb.append("\n");
}
return sb.toString().trim();
}
}

// point class
//
public static class Point implements Comparable<Point>
{
public double y;
public double x;

public Point(double x, double y)
{
this.x = x;
this.y = y;
}

public Point(Point point)
{
this.x = point.x;
this.y = point.y;
}

public double angle(Point base)
{
return Math.atan2((double) (y - base.y), (double) (x - base.x));
}

@Override
public String toString()
{
return String.format("%.5f %.5f", x, y);
}

public static double dist(Point point, Point point2)
{
return Math.hypot(point.x - point2.x, point.y - point2.y);
}

public void moveBack(Point p)
{
x -= p.x;
y -= p.y;
}

// r exp(i phi) = r cos(phi) + r i sin(phi)
public void rotate(double cAngle)
{
double r = dist(nullPoint, this);
double phi = angle(nullPoint) + cAngle;
x = Math.cos(phi) * r;
y = Math.sin(phi) * r;
}

public void scale(double cFactor)
{
x *= cFactor;
y *= cFactor;
}

public void move(Point p)
{
x += p.x;
y += p.y;
}

public static Point interpolate(Point start, Point end, double factor)
{
Point result = new Point(end);
result.moveBack(start);
result.scale(factor);
result.move(start);
return result;
}

@Override
public int compareTo(Point o)
{
if (Math.abs(x - o.x) < 1e-8)
if (Math.abs(y - o.y) < 1e-8)
return 0;
else
return y > o.y ? 1 : -1;
return x > o.x ? 1 : -1;
}
}

public static void main(String... as) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

// number of test cases
double depth;
int cases = 1;
LinkedList<Point> pointlist = new LinkedList<Point>();
TreeSet<Point> pointset = new TreeSet<Point>();
Matrix transmat = new Matrix();
StringBuilder sb = new StringBuilder();
String[] ina;

// solve all test cases
while (true)
{
ina = br.readLine().split(" ");
terminalPoint1 = new Point(Double.parseDouble(ina[0]), Double.parseDouble(ina[1]));
terminalPoint2 = new Point(Double.parseDouble(ina[2]), Double.parseDouble(ina[3]));
depth = Double.parseDouble(ina[4]);
pointlist.clear();
pointset.clear();

if (depth >= 1)
{
if (Point.dist(terminalPoint1, terminalPoint2) < depth)
{
// post 0 points if the basic line is too short
} else
{

firstPoint = Point.interpolate(terminalPoint1,
terminalPoint2, 1.0 / 4);
lastPoint = Point.interpolate(terminalPoint1,
terminalPoint2, 3.0 / 4);

tempP = new Point(lastPoint);
tempP.moveBack(firstPoint);
tempP.rotate(Math.PI / 3);
tempP.move(firstPoint);

// post only the basic line if the next level would be too short
if (Point.dist(tempP, firstPoint) - depth < 1e-8)
{
pointset.add(terminalPoint1);
pointset.add(terminalPoint2);
} else // calculate the fractal and post it
{

pointlist.add(terminalPoint1);
pointlist.add(firstPoint);
pointlist.add(tempP);
pointlist.add(lastPoint);
pointlist.add(terminalPoint2);

baseformLength = Point.dist(terminalPoint1,
terminalPoint2);

// calculate the coordinates of one line
calcFractal(pointlist, firstPoint, tempP, depth);

// and then transform the generated points to the other side
pointlist.remove(terminalPoint1);
pointlist.remove(firstPoint);
pointlist.remove(tempP);
pointlist.remove(lastPoint);
pointlist.remove(terminalPoint2);

// transformation matrix.
// moves the points to (0,0), rotates them and moves them back.
transmat = new Matrix();
transmat.move(lastPoint.x, lastPoint.y);
transmat.rotate(-2 * Math.PI / 3);
transmat.move(-tempP.x, -tempP.y);

// apply the matrix to all points generated in the previous calcFractal step
int s = pointlist.size();
pointset.addAll(pointlist);
for (int i = 0; i < s; i++)
{
pointset.add(transmat.mult(new Point(pointlist
.get(i))));
}
pointset.add(terminalPoint1);
pointset.add(firstPoint);
pointset.add(tempP);
pointset.add(lastPoint);
pointset.add(terminalPoint2);
}
}

// Stringbuffer necessary, no System.outs!
sb = new StringBuilder();
sb.append("Case " + (cases++) + ":\n");
sb.append(pointset.size());

// no collection sort here, too slow. use of TreeSet necessary!
//Collections.sort(pointlist);

// post the fractal
for (Point p : pointset)
{
sb.append("\n");
sb.append(p.toString());
}
System.out.println(sb.toString());
} else
break;
}
}

// calculates the complete fractal part on the given line (start->end)
private static void calcFractal(LinkedList<Point> pointlist, Point start,
Point end, double depth)
{
Point t1, t2, temp;

t1 = Point.interpolate(start, end, 1.0 / 4);
t2 = Point.interpolate(start, end, 3.0 / 4);

temp = new Point(t2);
temp.moveBack(t1);
temp.rotate(Math.PI / 3);
temp.move(t1);

double len = Point.dist(t1, temp);

if (depth < len)
{
pointlist.add(t1);
pointlist.add(temp);
pointlist.add(t2);

// calculate the points of the first line generated
int s = pointlist.size();
calcFractal(pointlist, t1, temp, depth);
s = pointlist.size() - s;

// ... and transform the recursively generated points to the other side
Matrix transmat;
transmat = new Matrix();
transmat.move(t2.x, t2.y);
transmat.rotate(-2 * Math.PI / 3);
transmat.move(-temp.x, -temp.y);

int oldsize = pointlist.size();
for (int i = pointlist.size() - s; i < oldsize; i++)
{
pointlist.add(transmat.mult(new Point(pointlist.get(i))));
}
} else
{
return;
}
}
}



2.

/**
* ACM Training 2009
* ACM Problem #10609 - Fractal
* Link: http://uva.onlinejudge.org/external/106/10609.html
*
* @author Felix Dietrich
* @version 1.0, 01/20/2010
*
* Methode: Matrix transformation, Fractals Bruteforce, StringBuffer, TreeSets
* Status : TLE
* Runtime: > 3 sec
*/

import java.io.IOException;
import java.util.LinkedList;
import java.util.Locale;
import java.util.Scanner;
import java.util.TreeSet;

public class Main
{
public static Point nullPoint = new Point(0, 0);
public static Point firstPoint;
public static Point lastPoint;
public static Point terminalPoint1;
public static Point terminalPoint2;
public static double baseformLength;
public static Point tempP;

/**
* 3x3 matrix class to transform points
*/
public static class Matrix
{
double[][] components;

/**
* Initializes the matrix with the identity matrix.
*/
public Matrix()
{
int rows = 3;
int cols = 3;
components = new double[rows][cols];
// create identity matrix
for (int i = 0; i < rows; i++)
for (int k = 0; k < rows; k++)
if (i != k)
components[i][k] = 0.0;
else
components[i][k] = 1.0;
}

/**
* scales this matrix by the given factor.
*
* @param f
* factor
*/
public void scale(double f)
{
Matrix m = new Matrix();
m.components[0][0] = f;
m.components[1][1] = f;

this.mult(m);
}

/**
* rotates the matrix by the given angle.
*
* @param phi
* angle
*/
public void rotate(double phi)
{
Matrix m = new Matrix();
m.components[0][0] = Math.cos(phi);
m.components[0][1] = -Math.sin(phi);
m.components[1][0] = Math.sin(phi);
m.components[1][1] = Math.cos(phi);

this.mult(m);
}

/**
* moves the matrix by the given deltas. note that the z coordinate
* cannot be given because the matrix is used for 2dim vectors.
*
* @param dx
* @param dy
*/
public void move(double dx, double dy)
{
Matrix m = new Matrix();
m.components[0][2] = dx;
m.components[1][2] = dy;

this.mult(m);
}

/**
* multiplies a matrix with the current and stores the result in this
* matrix.
*
* @param matrix
* to be multiplied to the right side of this matrix.
*/
public void mult(Matrix matrix)
{
Matrix result = new Matrix();
result.components[0][0] = 0;
for (int k = 0; k < 3; k++)
result.components[0][0] += components[0][k]
* matrix.components[k][0];
result.components[0][1] = 0;
for (int k = 0; k < 3; k++)
result.components[0][1] += components[0][k]
* matrix.components[k][1];
result.components[0][2] = 0;
for (int k = 0; k < 3; k++)
result.components[0][2] += components[0][k]
* matrix.components[k][2];
result.components[1][0] = 0;
for (int k = 0; k < 3; k++)
result.components[1][0] += components[1][k]
* matrix.components[k][0];
result.components[1][1] = 0;
for (int k = 0; k < 3; k++)
result.components[1][1] += components[1][k]
* matrix.components[k][1];
result.components[1][2] = 0;
for (int k = 0; k < 3; k++)
result.components[1][2] += components[1][k]
* matrix.components[k][2];
result.components[2][0] = 0;
for (int k = 0; k < 3; k++)
result.components[2][0] += components[2][k]
* matrix.components[k][0];
result.components[2][1] = 0;
for (int k = 0; k < 3; k++)
result.components[2][1] += components[2][k]
* matrix.components[k][1];
result.components[2][2] = 0;
for (int k = 0; k < 3; k++)
result.components[2][2] += components[2][k]
* matrix.components[k][2];
this.components = result.components;
}

/**
* multiplies this matrix with the given vector p and stores the result
* in p. the point p is a 2dim vector, the matrix 3x3. this means that p
* is extended to 3 dimensions, multiplied and then projected on 2
* dimensions by cutting off the 3rd.
*
* @param p
* point to multiply this matrix with
*/
public Point mult(Point p)
{
double x = p.x * components[0][0] + p.y * components[0][1]
+ components[0][2];
double y = p.x * components[1][0] + p.y * components[1][1]
+ components[1][2];
p.x = x;
p.y = y;
return p;
}

/**
* prints the matrix.
*/
public String toString()
{
StringBuffer sb = new StringBuffer();
for (int lrows = 0; lrows < 3; lrows++)
{
for (int lcols = 0; lcols < 3; lcols++)
{
sb.append(components[lrows][lcols]);
sb.append(" ");
}
sb.append("\n");
}
return sb.toString().trim();
}
}

// point class
//
public static class Point implements Comparable<Point>
{
public double y;
public double x;

public Point(double x, double y)
{
this.x = x;
this.y = y;
}

public Point(Point point)
{
this.x = point.x;
this.y = point.y;
}

public double angle(Point base)
{
return Math.atan2((double) (y - base.y), (double) (x - base.x));
}

@Override
public String toString()
{
return String.format("%.5f %.5f", x, y);
}

public static double dist(Point point, Point point2)
{
return Math.hypot(point.x - point2.x, point.y - point2.y);
}

public void moveBack(Point p)
{
x -= p.x;
y -= p.y;
}

// r exp(i phi) = r cos(phi) + r i sin(phi)
public void rotate(double cAngle)
{
double r = dist(nullPoint, this);
double phi = angle(nullPoint) + cAngle;
x = Math.cos(phi) * r;
y = Math.sin(phi) * r;
}

public void scale(double cFactor)
{
x *= cFactor;
y *= cFactor;
}

public void move(Point p)
{
x += p.x;
y += p.y;
}

public static Point interpolate(Point start, Point end, double factor)
{
Point result = new Point(end);
result.moveBack(start);
result.scale(factor);
result.move(start);
return result;
}

@Override
public int compareTo(Point o)
{
if (Math.abs(x - o.x) < 1e-8)
if (Math.abs(y - o.y) < 1e-8)
return 0;
else
return y > o.y ? 1 : -1;
return x > o.x ? 1 : -1;
}
}

public static void main(String... as) throws IOException
{
Scanner sc;
sc = new Scanner(System.in);
sc.useLocale(Locale.ENGLISH);
Locale.setDefault(Locale.ENGLISH);

// number of test cases
double depth;
int cases = 1;
LinkedList<Point> pointlist = new LinkedList<Point>();
TreeSet<Point> pointset = new TreeSet<Point>();
Matrix transmat = new Matrix();
StringBuffer sb = new StringBuffer();

// solve all test cases
while (true)
{
terminalPoint1 = new Point(sc.nextDouble(), sc.nextDouble());
terminalPoint2 = new Point(sc.nextDouble(), sc.nextDouble());
depth = sc.nextDouble();
pointlist.clear();
pointset.clear();

if (depth >= 1)
{
if (Point.dist(terminalPoint1, terminalPoint2) < depth)
{
// post 0 points if the basic line is too short
} else
{

firstPoint = Point.interpolate(terminalPoint1,
terminalPoint2, 1.0 / 4);
lastPoint = Point.interpolate(terminalPoint1,
terminalPoint2, 3.0 / 4);

tempP = new Point(lastPoint);
tempP.moveBack(firstPoint);
tempP.rotate(Math.PI / 3);
tempP.move(firstPoint);

// post only the basic line if the next level would be too short
if (Point.dist(tempP, firstPoint) - depth < 1e-8)
{
pointset.add(terminalPoint1);
pointset.add(terminalPoint2);
} else // calculate the fractal and post it
{

pointlist.add(terminalPoint1);
pointlist.add(firstPoint);
pointlist.add(tempP);
pointlist.add(lastPoint);
pointlist.add(terminalPoint2);

baseformLength = Point.dist(terminalPoint1,
terminalPoint2);

// calculate the coordinates of one line
calcFractal(pointlist, firstPoint, tempP, depth);

// and then transform the generated points to the other side
pointlist.remove(terminalPoint1);
pointlist.remove(firstPoint);
pointlist.remove(tempP);
pointlist.remove(lastPoint);
pointlist.remove(terminalPoint2);

// transformation matrix.
// moves the points to (0,0), rotates them and moves them back.
transmat = new Matrix();
transmat.move(lastPoint.x, lastPoint.y);
transmat.rotate(-2 * Math.PI / 3);
transmat.move(-tempP.x, -tempP.y);

// apply the matrix to all points generated in the previous calcFractal step
int s = pointlist.size();
pointset.addAll(pointlist);
for (int i = 0; i < s; i++)
{
pointset.add(transmat.mult(new Point(pointlist
.get(i))));
}
pointset.add(terminalPoint1);
pointset.add(firstPoint);
pointset.add(tempP);
pointset.add(lastPoint);
pointset.add(terminalPoint2);
}
}

// Stringbuffer necessary, no System.outs!
sb = new StringBuffer();
sb.append("Case " + (cases++) + ":\n");
sb.append(pointset.size());

// no collection sort here, too slow. use of TreeSet necessary!
//Collections.sort(pointlist);

// post the fractal
for (Point p : pointset)
{
sb.append("\n");
sb.append(p.toString());
}
System.out.println(sb.toString());
} else
return;
}
}

// calculates the complete fractal part on the given line (start->end)
private static void calcFractal(LinkedList<Point> pointlist, Point start,
Point end, double depth)
{
Point t1, t2, temp;

t1 = Point.interpolate(start, end, 1.0 / 4);
t2 = Point.interpolate(start, end, 3.0 / 4);

temp = new Point(t2);
temp.moveBack(t1);
temp.rotate(Math.PI / 3);
temp.move(t1);

double len = Point.dist(t1, temp);

if (depth < len)
{
pointlist.add(t1);
pointlist.add(temp);
pointlist.add(t2);

// calculate the points of the first line generated
int s = pointlist.size();
calcFractal(pointlist, t1, temp, depth);
s = pointlist.size() - s;

// ... and transform the recursively generated points to the other side
Matrix transmat;
transmat = new Matrix();
transmat.move(t2.x, t2.y);
transmat.rotate(-2 * Math.PI / 3);
transmat.move(-temp.x, -temp.y);

int oldsize = pointlist.size();
for (int i = pointlist.size() - s; i < oldsize; i++)
{
pointlist.add(transmat.mult(new Point(pointlist.get(i))));
}
} else
{
return;
}
}
}