Advertisement
Guest User

Untitled

a guest
Jan 26th, 2015
173
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.93 KB | None | 0 0
  1. public class ArmyTeleportation {
  2.   String yes = "possible";
  3.   String no = "impossible";
  4.   int n, m = 3;
  5.  
  6.   boolean possibleEven(int[] x1, int[] y1, int[] x2, int[] y2, int[] xt, int[] yt) {
  7.     int minx1 = min(x1);
  8.     int miny1 = min(y1);
  9.     int minx2 = min(x2);
  10.     int miny2 = min(y2);
  11.     for (int i = 0; i < n; i++) {
  12.       boolean found = false;
  13.       for (int j = 0; j < n; j++) {
  14.         if (x1[i] - minx1 == x2[j] - minx2 && y1[i] - miny1 == y2[j] - miny2) {
  15.           found = true;
  16.         }
  17.       }
  18.       if (!found) {
  19.         return false;
  20.       }
  21.     }
  22.     long x = minx2 - minx1;
  23.     long y = miny2 - miny1;
  24.     if (x % 2 != 0 || y % 2 != 0) {
  25.       return false;
  26.     }
  27.     x /= 2;
  28.     y /= 2;
  29.     long xa = xt[1] - xt[0];
  30.     long ya = yt[1] - yt[0];
  31.     long xb = xt[2] - xt[0];
  32.     long yb = yt[2] - yt[0];
  33.     if (xa * yb != xb * ya) {
  34.       long a = (x * yb - y * xb);
  35.       long b = (x * ya - y * xa);
  36.       long c = (xa * yb - ya * xb);
  37.       return (a % c == 0) && (b % c == 0);
  38.     }
  39.     if (x * yb != xb * y) {
  40.       return false;
  41.     }
  42.     if (xa == 0) {
  43.       long t = xa; xa = ya; ya = t;
  44.       t = xb; xb = yb; yb = t;
  45.       t = x; x = y; y = t;
  46.     }
  47.     long g = gcd(Math.abs(xa), Math.abs(xb));
  48.     return x % g == 0;
  49.   }
  50.  
  51.   public static long gcd(long a, long b) {
  52.     while (a > 0) {
  53.       long t = b % a;
  54.       b = a;
  55.       a = t;
  56.     }
  57.     return b;
  58.   }
  59.  
  60.   int min(int[] x) {
  61.     int res = Integer.MAX_VALUE;
  62.     for (int i : x) {
  63.       res = Math.min(res, i);
  64.     }
  65.     return res;
  66.   }
  67.  
  68.   public String ifPossible(int[] x1, int[] y1, int[] x2, int[] y2, int[] xt, int[] yt) {
  69.     n = x1.length;
  70.     boolean p1 = possibleEven(x1, y1, x2, y2, xt, yt);
  71.     for (int i = 0; i < n; i++) {
  72.       x1[i] = 2 * xt[0] - x1[i];
  73.       y1[i] = 2 * yt[0] - y1[i];
  74.     }
  75.     boolean p2 = possibleEven(x1, y1, x2, y2, xt, yt);
  76.     return (p1 || p2) ? yes : no;
  77.   }
  78.  
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement