2013
11-13

# Fractal

Fractals are really cool mathematical objects. They have a lot of interesting properties, often including:

1. fine structure at arbitrarily small scales;

2. self-similarity, i.e., magnified it looks like a copy of itself;

3. a simple, recursive definition.

Approximate fractals are found a lot in nature, for example, in structures such as clouds, snow flakes, mountain ranges, and river networks.

In this problem, we consider fractals generated by the following algorithm: we start with a polyline, i.e., a set of connected line segments. This is what we call a fractal of depth one (see leftmost picture). To obtain a fractal of depth two, we replace each line segment with a scaled and rotated version of the original polyline (see middle picture). By repetitively replacing the line segments with the polyline, we obtain fractals of arbitrary depth and very fine structures arise. The rightmost picture shows a fractal of depth three.

The complexity of an approximate fractal increases quickly as its depth increases. We want to know where we end up after traversing a certain fraction of its length.

The input starts with a single number c (1 <= c <= 200) on one line, the number of test cases. Then each test case starts with one line with n (3 <= n <= 100), the number of points of the polyline. Then follow n lines with on the ith line two integers xi and yi ( -1 000 <= xi, yi <= 1 000), the consecutive points of the polyline. Next follows one line with an integer d (1 <= d <= 10), the depth of the fractal. Finally, there is one line with a floating point number f (0 <= f <= 1), the fraction of the length thatis traversed.

The length of each line segment of the polyline is smaller than the distance between the first point (x1, y1) and the last point (xn, yn) of the polyline. The length of the complete polyline is smaller than twice this distance.

Per test case, the output contains one line with the coordinate where we end up. Format it as (x,y), with two floating point numbers x and y. The absolute error in both coordinates should be smaller than 10-6.

1
4
-2 -2
0 0
0 2
2 2
3
0.75

(0.4267766953,2)

//* @author:
import java.io.*;
import java.util.*;
import java.math.*;

public class Main
{
static class complex
{
double x, y;
complex (double x0, double y0)
{
x = x0; y = y0;
}
complex () { x = 0; y = 0; }
{
return new complex(x + b.x, y + b.y);
}
complex minus (complex b)
{
return new complex(x - b.x, y - b.y);
}
complex multiply (complex b)
{
return new complex(x * b.x - y * b.y, x * b.y + y * b.x);
}
complex divide (complex b)
{
return new complex((x * b.x + y * b.y) / (b.x * b.x + b.y * b.y),
(y * b.x - x * b.y) / (b.x * b.x + b.y * b.y));
}
}

static double distance (complex a, complex b)
{
return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
static final double eps = 1e-12;
static double total_length;
static complex [] linepoint = new complex[110];
static int mvert;
static complex rate (complex a, complex b, double r)
{
return new complex(a.x * (1 - r) + b.x * r,a.y * (1 - r) + b.y * r);
}

static complex transport (complex v, complex ori, complex tar)
{
complex res = tar.divide(ori);
return res.multiply(v);
}

static complex fractal (int depth, int mdepth, double r)
{
double tl = total_length * r;
for (int i = 1; i < mvert; i++)
{
if (Math.abs(tl) < eps) return linepoint[i - 1];
double d = distance(linepoint[i - 1], linepoint[i]);
if (tl - d < eps)
{
if (depth == mdepth) return rate(linepoint[i - 1], linepoint[i], tl / d);
else
{
complex res = fractal(depth + 1, mdepth, tl / d);
complex rv = transport(res.minus(linepoint[0]),
linepoint[mvert - 1].minus(linepoint[0]),
linepoint[i].minus(linepoint[i - 1]));
}
}
else tl -= d;
}
return linepoint[mvert - 1];
}

public static void main (String args[]) throws Exception
{
for (int kase = Integer.parseInt(ln); kase > 0; --kase)
{
for (int i = 0; i < mvert; i++)
{
StringTokenizer token = new StringTokenizer(ln);
int x = Integer.parseInt(token.nextToken());
int y = Integer.parseInt(token.nextToken());
linepoint[i] = new complex(x, y);
}
total_length = 0;
for (int i = 1; i < mvert; i++) total_length += distance(linepoint[i], linepoint[i - 1]);
complex res = fractal(1, mdep, rt);
System.out.printf("(%.10f,%.10f)%n", res.x, res.y);
}
}
}

1. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”

2. 漂亮。佩服。
P.S. unsigned 应该去掉。换行符是n 不是/n
还可以稍微优化一下，
int main() {
int m,n,ai,aj,bi,bj,ak,bk;
while (scanf("%d%d",&m,&n)!=EOF) {
ai = sqrt(m-1);
bi = sqrt(n-1);
aj = (m-ai*ai-1)>>1;
bj = (n-bi*bi-1)>>1;
ak = ((ai+1)*(ai+1)-m)>>1;
bk = ((bi+1)*(bi+1)-n)>>1;
printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
}
}