1. 

/**
* ACM Training 2009
* ACM Problem #ICPC NWERC Problem D - Fractals
*
* @author Felix Dietrich
* @version 1.0, 1/5/2010
*
* Methode: recursion, matrix translation, complex numbers, fractals
* Status : Accepted (Test Set)
* Runtime:
* Link: http://2009.nwerc.eu/results/nwerc09.pdf
*/

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import java.util.Scanner;

public class Main
{
/**
* 3x3 matrix class to translate 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();
for (int lrows = 0; lrows < 3; lrows++)
{
for (int lcols = 0; lcols < 3; lcols++)
{
result.components[lrows][lcols] = 0;
for (int k = 0; k < 3; k++)
result.components[lrows][lcols] += components[lrows][k]
* matrix.components[k][lcols];
}
}
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 void 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;
}

/**
* 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();
}
}

public static Point nullPoint = new Point(0, 0);
public static Point firstPoint;
public static Point lastPoint;
public static double baseformLength;
public static double baseformDist;
private static Point cP;
private static Point cP2;

/**
* Point class, representing a 2 dim. point in coordinate space.
* The class has functions to calc the dist between points and
* to interpolate a point between two points.
*/
public static class Point
{
public double y;
public double x;

/**
* Defctor.
* @param x2
* @param y2
*/
public Point(int x2, int y2)
{
this.x = (int) x2;
this.y = (int) y2;
}

/**
* Copyctor.
* @param point
*/
public Point(Point point)
{
this.x = point.x;
this.y = point.y;
}

/**
* Calculates the angle between this and the given vector
* ("points" are seen as vectors here).
* @param base the vector the angle is starting from
* @return angle
*/
public double angle(Point base)
{
return Math.atan2((double) (y - base.y), (double) (x - base.x));
}

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

/**
* calculates the euclidian distance between point and point2
* @param point
* @param point2
* @return distance
*/
public static double dist(Point point, Point point2)
{
return Math.hypot(point.x - point2.x, point.y - point2.y);
}

/**
* Moves this point back by the given point coordinates.
* @param p
*/
public void moveBack(Point p)
{
x -= p.x;
y -= p.y;
}

/**
* Rotates the point, using complex representation.
* r exp(i phi) = r cos(phi) + r i sin(phi)
* @param angle angle to rotate (clockwise)
*/
public void rotate(double angle)
{
double r = dist(nullPoint, this);
double phi = angle(nullPoint) + angle;
x = Math.cos(phi) * r;
y = Math.sin(phi) * r;
}

/**
* Scales the point by the given factor.
* @param f factor
*/
public void scale(double f)
{
x *= f;
y *= f;
}

/**
* Moves the point by the coordinates of the given point.
* @param p
*/
public void move(Point p)
{
x += p.x;
y += p.y;
}

/**
* Interpolates between the two given points, by the given factor.
* @param start
* @param end
* @param factor
* @return the point at the interpolated position
*/
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;
}
}

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 testcases
int cases = sc.nextInt();
int points;
int depth;
double fraction;
List<Point> pointlist = new ArrayList<Point>();

// solve all testcases
for (int k = 0; k < cases; k++)
{
// point count for start
points = sc.nextInt();
baseformLength = 0;
cP2 = null;
pointlist.clear();
// points on the polyline with depth = 1
for (int i = 0; i < points; i++)
{
cP = new Point(sc.nextInt(), sc.nextInt());
pointlist.add(cP);
if (cP2 != null)
baseformLength += Point.dist(cP, cP2);
cP2 = cP;
}
// end depth of the fractal
depth = sc.nextInt();
// traversal fraction of the length
fraction = sc.nextDouble();

firstPoint = pointlist.get(0);
lastPoint = pointlist.get(points - 1);

// calculate the required point on the fractal
Point l = calcFractalPoint(pointlist, baseformLength, fraction, depth);

System.out.println(l);
}
}

private static double eps = 1e-11;

/**
* Most important function of the program.
* The algorithm works like this:
* - add up the length until we reach the desired fraction
* - save the end points of the current line segment
* and calculate the new fraction
* - create a translation matrix to apply on all points
* - transform the points to the found line segment
* - decrease depth and recall the algo recursively
*
* @param pointlist points of the fractal base form
* @param length total sum of the length of the line segments
* @param frac fraction we should traverse the length
* @param depth fractal depth
* @return a point where we end up traversing the length
*/
private static Point calcFractalPoint(List<Point> pointlist, double length,
double frac, int depth)
{
firstPoint = pointlist.get(0);
lastPoint = pointlist.get(pointlist.size() - 1);

baseformDist = Point.dist(firstPoint, lastPoint);

if (frac == 0.0)
return new Point(firstPoint);
if (frac == 1.0)
return new Point(lastPoint);

double cLen = length * frac;

if (cLen <= 0)
return new Point(firstPoint);

cP = null;
cP2 = null;
// find points p and p-1 where the fraction length point lies in between
for (int i = 0; i < pointlist.size(); i++)
{
cP = pointlist.get(i);
if (cP2 != null)
cLen -= Point.dist(cP, cP2);
if (cLen <= 0)
break;
cP2 = cP;
}

// calc new fraction. + cause cLen is negative!
frac = (Point.dist(cP, cP2) + cLen) / Point.dist(cP, cP2);

if (Math.abs(frac) < eps)
return new Point(cP2);
if (Math.abs(frac - 1.0) < eps)
return new Point(cP);

if (depth == 1)
{
return Point.interpolate(cP2, cP, frac);
}

// calc the translation matrix for the points. 3x3 cause we need moving.
Matrix tMat = new Matrix();
tMat.move(cP2.x, cP2.y);
// get the angle between the current points to know how to rotate
tMat.rotate(cP2.angle(cP) - firstPoint.angle(lastPoint));
tMat.scale(Point.dist(cP, cP2) / baseformDist);
tMat.move(-firstPoint.x, -firstPoint.y);

cP2 = null;
length = 0.0;
// apply the matrix to all vectors in the list while calculating the new length.
for (Point p : pointlist)
{
tMat.mult(p);
cP = p;
if (cP2 != null)
length += Point.dist(cP, cP2);
cP2 = cP;
}
length += Point.dist(cP, cP2);

depth--;
return calcFractalPoint(pointlist, length, frac, depth);
}
}