package adv2017; import java.awt.geom.Point2D; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.math.BigDecimal; import java.math.MathContext; import java.util.Arrays; import java.util.InputMismatchException; public class N620_2 { InputStream is; PrintWriter out; String INPUT = ""; MathContext mc = new MathContext(40); void solve() { int U = ni(); if(!(1 <= U && U <= 1000))throw new AssertionError("U"); for(;U > 0;U--){ int T = ni(); BigDecimal P = new BigDecimal(ns(), mc); BigDecimal OMEGA = new BigDecimal(ns(), mc); BigDecimal V = new BigDecimal(ns(), mc); BigDecimal GX = new BigDecimal(ns(), mc); BigDecimal GY = new BigDecimal(ns(), mc); if(!(1 <= T && T <= 15))throw new AssertionError("T"); if(!(0 <= P.doubleValue() && P.doubleValue() <= 1e9))throw new AssertionError("P"); if(!(-10 <= OMEGA.doubleValue() && OMEGA.doubleValue() <= 10))throw new AssertionError("omega"); if(!(-10 <= V.doubleValue() && V.doubleValue() <= 10))throw new AssertionError("v"); if(!(-100 <= GX.doubleValue() && GX.doubleValue() <= 100))throw new AssertionError("gx"); if(!(-100 <= GY.doubleValue() && GY.doubleValue() <= 100))throw new AssertionError("gy"); /* (1+v -ω ux) (ω 1+v uy) (0 0 1) * */ BigDecimal[][] M = { {BigDecimal.ONE.add(V), OMEGA.negate()}, {OMEGA, BigDecimal.ONE.add(V)} }; BigDecimal[][] E = { {BigDecimal.ONE, BigDecimal.ZERO}, {BigDecimal.ZERO, BigDecimal.ONE} }; BigDecimal[][][] MS = new BigDecimal[T+1][][]; MS[0] = E; for(int i = 1;i <= T;i++){ MS[i] = mul(MS[i-1], M, mc); } BigDecimal[][] Q = new BigDecimal[2*T+2][2*T+2]; for(int i = 0;i < 2*T+2;i++){ for(int j = 0;j < 2*T+2;j++){ Q[i][j] = BigDecimal.ZERO; } } for(int i = 0;i < 2*T;i++){ Q[i][i] = BigDecimal.ONE; } // Q = I // c = 0 // E = MS[T-1] MS[T-2] MS[T-3] ... for(int i = 0;i < T;i++){ for(int j = 0;j < 2;j++){ for(int k = 0;k < 2;k++){ Q[2*i+k][2*T+j] = Q[2*T+j][2*i+k] = MS[T-1-i][j][k]; } } } BigDecimal[] d = new BigDecimal[2*T+2]; for(int i = 0;i < 2*T;i++)d[i] = BigDecimal.ZERO; d[2*T] = GX.subtract(MS[T][0][0]); d[2*T+1] = GY.subtract(MS[T][1][0]); // tr(MS[T]); Result res = gaussElimination(Q, d, BigDecimal.ZERO, mc); BigDecimal[] x = res.sol; check(OMEGA, V, x, T, GX, GY, P, mc); for(int i = 0;i < 2*T;i+=2){ out.printf("%.40f %.40f\n", x[i], x[i+1]); } } } static void check(BigDecimal OMEGA, BigDecimal V, BigDecimal[] x, int T, BigDecimal GX, BigDecimal GY, BigDecimal P, MathContext mc) { BigDecimal[] v = new BigDecimal[]{BigDecimal.ONE, BigDecimal.ZERO, BigDecimal.ONE}; BigDecimal used = BigDecimal.ZERO; for(int i = 0;i < T;i++){ used = used.add(x[i*2].multiply(x[i*2], mc)); used = used.add(x[i*2+1].multiply(x[i*2+1], mc)); BigDecimal[][] M = { {BigDecimal.ONE.add(V), OMEGA.negate(), x[i*2]}, {OMEGA, BigDecimal.ONE.add(V), x[i*2+1]}, {BigDecimal.ZERO, BigDecimal.ZERO, BigDecimal.ONE} }; v = mul(M, v, mc); } // tr(used, P); //// assert used <= P; // tr(v, GX, GY); if(!(Point2D.distance(v[0].doubleValue(), v[1].doubleValue(), GX.doubleValue(), GY.doubleValue()) <= 1e-4))throw new RuntimeException(); } public static BigDecimal[] mul(BigDecimal[][] A, BigDecimal[] v, MathContext mc) { int m = A.length; int n = v.length; BigDecimal[] w = new BigDecimal[m]; for(int i = 0;i < m;i++){ BigDecimal sum = BigDecimal.ZERO; for(int k = 0;k < n;k++){ sum = sum.add(A[i][k].multiply(v[k], mc), mc); } w[i] = sum; } return w; } public static BigDecimal[][] p2(BigDecimal[][] A, MathContext mc) { int n = A.length; BigDecimal[][] C = new BigDecimal[n][n]; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ C[i][j] = BigDecimal.ZERO; } } for(int i = 0;i < n;i++){ for(int k = 0;k < n;k++){ for(int j = 0;j < n;j++){ C[i][j] = C[i][j].add(A[i][k].multiply(A[k][j], mc), mc); } } } return C; } // A^e*v public static BigDecimal[] pow(BigDecimal[][] A, BigDecimal[] v, long m, MathContext mc) { BigDecimal[][] mu = A; BigDecimal[] r = v; for(;m > 0;m>>>=1){ if((m&1)==1)r = mul(mu, r, mc); mu = p2(mu, mc); } return r; } // 普通の累乗計算セット ここまで // ret[n]=A^(2^n) public static BigDecimal[][][] generateP2(BigDecimal[][] A, int n, MathContext mc) { BigDecimal[][][] ret = new BigDecimal[n+1][][]; ret[0] = A; for(int i = 1;i <= n;i++)ret[i] = p2(ret[i-1], mc); return ret; } // A[0]^e*v // A[n]=A[0]^(2^n) public static BigDecimal[] pow(BigDecimal[][][] A, BigDecimal[] v, long e, MathContext mc) { for(int i = 0;e > 0;e>>>=1,i++) { if((e&1)==1)v = mul(A[i], v, mc); } return v; } // メモ累乗計算セット ここまで public static BigDecimal[][] add(BigDecimal[][] A, BigDecimal[][] B, MathContext mc) { int m = A.length; int n = A[0].length; BigDecimal[][] C = new BigDecimal[m][n]; for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ C[i][j] = A[i][j].add(B[i][j], mc); } } return C; } public static BigDecimal[][] sub(BigDecimal[][] A, BigDecimal[][] B, MathContext mc) { int m = A.length; int n = A[0].length; BigDecimal[][] C = new BigDecimal[m][n]; for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ C[i][j] = A[i][j].subtract(B[i][j], mc); } } return C; } // double行列の積 public static BigDecimal[][] mul(BigDecimal[][] A, BigDecimal[][] B, MathContext mc) { assert A[0].length == B.length; int m = A.length; int n = A[0].length; int o = B[0].length; BigDecimal[][] C = new BigDecimal[m][o]; for(int i = 0;i < m;i++){ for(int j = 0;j < o;j++){ C[i][j] = BigDecimal.ZERO; } } for(int i = 0;i < m;i++){ for(int k = 0;k < n;k++){ for(int j = 0;j < o;j++){ C[i][j] = C[i][j].add(A[i][k].multiply(B[k][j], mc), mc); } } } return C; } public static Result gaussElimination(BigDecimal[][] M, BigDecimal[] v, BigDecimal eps, MathContext mc) { int n = M.length, m = M[0].length; int[] head = new int[n]; // Forward Elimination int row = 0; for(int col = 0;col < m;col++){ // select pivot boolean pivotFound = false; out: for(int prow = row;prow < n;prow++){ if(M[prow][col].abs().compareTo(eps) > 0){ // pivot found if(prow != row){ // swap rows for(int k = 0;k < m;k++){ BigDecimal u = M[prow][k]; M[prow][k] = M[row][k]; M[row][k] = u; } BigDecimal dum = v[prow]; v[prow] = v[row]; v[row] = dum; } pivotFound = true; break out; } } if(!pivotFound)continue; head[row] = col; // diag to 1 BigDecimal imul = BigDecimal.ONE.divide(M[row][col], mc); for(int k = 0;k < m;k++)M[row][k] = M[row][k].multiply(imul, mc); v[row] = v[row].multiply(imul, mc); for(int j = row+1;j < n;j++){ if(M[j][col].abs().compareTo(eps) > 0){ BigDecimal mul = M[j][col].negate(); for(int k = col;k < m;k++){ M[j][k] = M[j][k].add(M[row][k].multiply(mul, mc), mc); } v[j] = v[j].add(v[row].multiply(mul), mc); } } row++; } Result ret = new Result(); ret.mat = M; for(int i = row;i < n;i++){ if(v[i].abs().compareTo(eps) > 0){ ret.rank = row; ret.exists = false; return ret; } } for(int i = row-1;i >= 0;i--){ for(int j = i-1;j >= 0;j--){ if(M[j][head[i]].abs().compareTo(eps) > 0){ BigDecimal mul = M[j][head[i]].negate(); for(int k = head[i];k < m;k++){ M[j][k] = M[j][k].add(M[i][k].multiply(mul, mc), mc); } v[j] = v[j].add(v[i].multiply(mul, mc), mc); } } } BigDecimal[] retv = new BigDecimal[m]; for(int i = 0;i < row;i++){ retv[head[i]] = v[i]; } ret.sol = retv; ret.rank = row; ret.exists = true; return ret; } public static class Result { public BigDecimal[][] mat; public BigDecimal[] sol; public int rank; public boolean exists; } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){ // @Override // public void run() { // long s = System.currentTimeMillis(); // solve(); // out.flush(); // if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // } // }; // t.start(); // t.join(); } public static void main(String[] args) throws Exception { new N620_2().run(); } private byte[] inbuf = new byte[1024]; public int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private long[] nal(int n) { long[] a = new long[n]; for(int i = 0;i < n;i++)a[i] = nl(); return a; } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[][] nmi(int n, int m) { int[][] map = new int[n][]; for(int i = 0;i < n;i++)map[i] = na(m); return map; } private int ni() { return (int)nl(); } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }