結果
問題 | No.471 直列回転機 |
ユーザー |
|
提出日時 | 2016-12-21 00:12:53 |
言語 | Java (openjdk 23) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,486 bytes |
コンパイル時間 | 3,657 ms |
コンパイル使用メモリ | 87,268 KB |
実行使用メモリ | 82,720 KB |
平均クエリ数 | 18780.53 |
最終ジャッジ日時 | 2024-07-16 11:30:27 |
合計ジャッジ時間 | 34,901 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 55 RE * 3 |
ソースコード
package adv2016;import java.io.PrintWriter;import java.util.Arrays;import java.util.Random;import java.util.Scanner;public class N471 {static Scanner in;static PrintWriter out;static String INPUT = "";static long[] get(long x, long y){out.println("? " + x + " " + y);out.flush();return new long[]{nl(), nl()};}static void solve(){int m = ni();double[][] rotr = new double[m][];for(int i = 0;i < m;i++){rotr[i] = new double[]{ni(), ni(), 1};}Random gen = new Random();long[][] res = new long[3][];long[] xs = new long[3];long[] ys = new long[3];for(int i = 0;i < 3;i++){xs[i] = gen.nextInt(20)-10;ys[i] = gen.nextInt(20)-10;res[i] = get(xs[i], ys[i]);// ax+by+c=x'}double[][] X = new double[3][];{double[][] M = new double[3][3];double[] v = new double[3];for(int i = 0;i < 3;i++){M[i][0] = xs[i];M[i][1] = ys[i];M[i][2] = 1;v[i] = res[i][0];}double[] ret = solve(M, v);X[0] = ret;}{double[][] M = new double[3][3];double[] v = new double[3];for(int i = 0;i < 3;i++){M[i][0] = xs[i];M[i][1] = ys[i];M[i][2] = 1;v[i] = res[i][1];}double[] ret = solve(M, v);X[1] = ret;}{double[][] M = new double[3][3];double[] v = new double[3];for(int i = 0;i < 3;i++){M[i][0] = xs[i];M[i][1] = ys[i];M[i][2] = 1;v[i] = 1;}double[] ret = solve(M, v);X[2] = ret;}// (a b c) (x)// (d e f) (y)// (g h i) (1)out.println("!");for(int i = 0;i < m;i++){double[] w = mul(X, rotr[i]);out.println(Math.round(w[0]) + " " + Math.round(w[1]));}}public static double[] mul(double[][] A, double[] v){int m = A.length;int n = v.length;double[] w = new double[m];for(int i = 0;i < m;i++){double sum = 0;for(int k = 0;k < n;k++){sum += A[i][k] * v[k];}w[i] = sum;}return w;}public static double[] solve(double[][] a, double[] c){int n = a.length;int[] ps = new int[n];for(int i = 0;i < n;i++)ps[i] = i;// Forward Eliminationfor(int i = 0;i < n;i++){int pivot = -1;int from = -1;double amax = 0;for(int j = i;j < n;j++){if(Math.abs(a[ps[j]][i]) > amax){amax = Math.abs(a[ps[j]][i]);pivot = ps[j];from = j;}}if(pivot == -1)return null;int d = ps[i]; ps[i] = ps[from]; ps[from] = d;for(int j = i+1;j < n;j++){a[ps[i]][j] /= a[ps[i]][i];}c[ps[i]] /= a[ps[i]][i];a[ps[i]][i] = 1.0;for(int j = i+1;j < n;j++){for(int k = i+1;k < n;k++){a[ps[j]][k] -= a[ps[j]][i] * a[ps[i]][k];}c[ps[j]] -= a[ps[j]][i] * c[ps[i]];a[ps[j]][i] = 0.0;}}// Back Substitutionfor(int i = n-1;i >= 0;i--){for(int j = i-1;j >= 0;j--){c[ps[j]] -= a[ps[j]][i] * c[ps[i]];}}double[] ret = new double[n];for(int i = 0;i < n;i++){ret[i] = c[ps[i]];}return ret;}public static void main(String[] args) throws Exception{in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT);out = new PrintWriter(System.out);solve();out.flush();}static int ni() { return Integer.parseInt(in.next()); }static long nl() { return Long.parseLong(in.next()); }static double nd() { return Double.parseDouble(in.next()); }static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }}