結果
| 問題 | No.62 リベリオン(Extra) |
| ユーザー |
 uwi
|
| 提出日時 | 2014-11-10 04:35:07 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,158 ms / 5,000 ms |
| コード長 | 5,629 bytes |
| コンパイル時間 | 2,752 ms |
| コンパイル使用メモリ | 89,808 KB |
| 実行使用メモリ | 64,728 KB |
| 最終ジャッジ日時 | 2024-12-31 09:21:26 |
| 合計ジャッジ時間 | 5,237 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 3 |
ソースコード
import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.math.BigInteger;import java.util.Arrays;import java.util.InputMismatchException;public class Main {static InputStream is;static PrintWriter out;static String INPUT = "";static void solve(){for(int T = ni();T >= 1;T--){int w = ni(), h = ni();int d = ni();int mx = ni(), my = ni();int hx = ni(), hy = ni();int vx = ni(), vy = ni();if(vx < 0){mx = w-mx;hx = w-hx;vx = -vx;}if(vy < 0){my = h-my;hy = h-hy;vy = -vy;}if(check(2*w, 2*h, mx, my, hx, hy, vx, vy, d) ||check(2*w, 2*h, 2*w-mx, my, hx, hy, vx, vy, d) ||check(2*w, 2*h, mx, 2*h-my, hx, hy, vx, vy, d) ||check(2*w, 2*h, 2*w-mx, 2*h-my, hx, hy, vx, vy, d)){out.println("Hit");}else{out.println("Miss");}}}static boolean check(long w2, long h2, long mx, long my, long hx, long hy, long vx, long vy, long d){if(vx == 0){long ty = my;if(ty < hy)ty += h2;return hx == mx && ty-hy <= d*vy;}if(vy == 0){long tx = mx;if(tx < hx)tx += w2;return hy == my && tx-hx <= d*vx;}// tr(hx, hy, mx, my, vx, vy, w2, h2);BigInteger[] eg = exGCD(b(w2*vy), b(-h2*vx));long c = (hx-mx)*vy-(hy-my)*vx;if(c % eg[0].longValue() != 0)return false;long ce = c / eg[0].longValue();BigInteger a = eg[1].multiply(b(ce));// tr(a, b, (a*w2-(hx-mx))*vy, (b*h2-(hy-my))*vx);BigInteger val = a.multiply(b(w2)).subtract(b(hx-mx));BigInteger unit = b(h2*vx/eg[0].longValue()).multiply(b(w2));return val.mod(unit).compareTo(b(d*vx)) <= 0;}public static BigInteger b(long x){ return BigInteger.valueOf(x); }public static BigInteger[] exGCD(BigInteger a, BigInteger b){if(a.signum() == 0 || b.signum() == 0)return null;int as = a.signum(), bs = b.signum();a = a.abs(); b = b.abs();BigInteger p = BigInteger.ONE, q = BigInteger.ZERO, r = BigInteger.ZERO, s = BigInteger.ONE;while(b.signum() > 0){BigInteger c = a.divide(b);BigInteger d;d = a; a = b; b = d.mod(b);d = p; p = q; q = d.subtract(c.multiply(q));d = r; r = s; s = d.subtract(c.multiply(s));}return new BigInteger[]{a, as == -1 ? p.negate() : p, bs == -1 ? r.negate() : r};}public static int gcd(int a, int b) {while (b > 0) {int c = a;a = b;b = c % b;}return a;}public static void main(String[] args) throws Exception{long S = System.currentTimeMillis();is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());out = new PrintWriter(System.out);solve();out.flush();long G = System.currentTimeMillis();tr(G-S+"ms");}private static boolean eof(){if(lenbuf == -1)return true;int lptr = ptrbuf;while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;try {is.mark(1000);while(true){int b = is.read();if(b == -1){is.reset();return true;}else if(!isSpaceChar(b)){is.reset();return false;}}} catch (IOException e) {return true;}}private static byte[] inbuf = new byte[1024];static int lenbuf = 0, ptrbuf = 0;private static 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 static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }private static double nd() { return Double.parseDouble(ns()); }private static char nc() { return (char)skip(); }private static 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 static 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 static 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 static int[] na(int n){int[] a = new int[n];for(int i = 0;i < n;i++)a[i] = ni();return a;}private static int ni(){int num = 0, 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 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) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }}