fork download
copy 
  1.  
  2.  
  3. import java.awt.geom.Line2D;
  4. import java.io.BufferedReader;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.util.ArrayList;
  8. import java.util.LinkedList;
  9. import java.util.List;
  10.  
  11. import static java.lang.Double.max;
  12. import static java.lang.Double.min;
  13.  
  14. public class Main {
  15.  
  16.     private static final double G = 9.80665;
  17.  
  18.     static class Building {
  19.         int x, y, z;
  20.         boolean visited;
  21.         int steps = 0;
  22.         int i, j;
  23.  
  24.         Building(int x, int y, int z, int i, int j) {
  25.             this.x = x;
  26.             this.y = y;
  27.             this.z = z;
  28.             this.i = i;
  29.             this.j = j;
  30.         }
  31.  
  32.         @Override
  33.         public String toString() {
  34.             return "Building{" +
  35.                     "x=" + x +
  36.                     ", y=" + y +
  37.                     ", z=" + z +
  38.                     '}';
  39.         }
  40.     }
  41.  
  42.     static class Segment {
  43.         double x1, y1, x2, y2;
  44.  
  45.         public Segment(double x1, double y1, double x2, double y2) {
  46.             this.x1 = x1;
  47.             this.y1 = y1;
  48.             this.x2 = x2;
  49.             this.y2 = y2;
  50.         }
  51.  
  52.         @Override
  53.         public String toString() {
  54.             return "(" + x1 + ", " + y1 + ") -> (" + x2 + ", " + y2 + ")";
  55.         }
  56.  
  57.         //        https://g...content-available-to-author-only...b.com/baobabKoodaa/CodeForcesLibrary/blob/ad6972b1ccd87c9100171122692562704c695703/src/baobab/A.java#L767
  58.         static final Point OVERLAP = new Point(0, 0);
  59.  
  60.         Point intersect(Segment s) {
  61.             // Returns true if segment 1-2 intersects segment 3-4
  62.             double x3 = s.x1, x4 = s.x2, y3 = s.y1, y4 = s.y2;
  63.  
  64.             if (x1 == x2 && x3 == x4) {
  65.                 // Both segments are vertical
  66.                 if (x1 != x3) {
  67.                     return null;
  68.                 }
  69.                 if (min(y1, y2) < min(y3, y4)) {
  70.                     if (max(y1, y2) >= min(y3, y4)) {
  71.                         return OVERLAP;
  72.                     } else {
  73.                         return null;
  74.                     }
  75.                 } else {
  76.                     if (max(y3, y4) >= min(y1, y2)) {
  77.                         return OVERLAP;
  78.                     } else {
  79.                         return null;
  80.                     }
  81.                 }
  82.             }
  83.             if (x1 == x2) {
  84.                 // Only segment 1-2 is vertical. Does segment 3-4 cross it? y = a*x + b
  85.                 double a34 = (y4 - y3) / (x4 - x3);
  86.                 double b34 = y3 - a34 * x3;
  87.                 double y = a34 * x1 + b34;
  88.                 if (y >= min(y1, y2) - 1e-6 && y <= max(y1, y2)  + 1e-6 && x1 >= min(x3, x4) - 1e-6 && x1 <= max(x3, x4) + 1e-6) {
  89.                     return new Point(x1, y);
  90.                 } else {
  91.                     return null;
  92.                 }
  93.             }
  94.             if (x3 == x4) {
  95.                 // Only segment 3-4 is vertical. Does segment 1-2 cross it? y = a*x + b
  96.                 double a12 = (y2 - y1) / (x2 - x1);
  97.                 double b12 = y1 - a12 * x1;
  98.                 double y = a12 * x3 + b12;
  99.                 if (y >= min(y3, y4) - 1e-6 && y <= max(y3, y4) + 1e-6 && x3 >= min(x1, x2) - 1e-6 && x3 <= max(x1, x2) + 1e-6) {
  100.                     return new Point(x3, y);
  101.                 } else {
  102.                     return null;
  103.                 }
  104.             }
  105.             double a12 = (y2 - y1) / (x2 - x1);
  106.             double b12 = y1 - a12 * x1;
  107.             double a34 = (y4 - y3) / (x4 - x3);
  108.             double b34 = y3 - a34 * x3;
  109.             if (closeToZero(a12 - a34)) {
  110.                 // Parallel lines
  111.                 if (closeToZero(b12 - b34)) {
  112.                     return OVERLAP;
  113.                 } else {
  114.                     return null;
  115.                 }
  116.             }
  117.             // Non parallel non vertical lines intersect at x. Is x part of both segments?
  118.             double x = -(b12 - b34) / (a12 - a34);
  119.             if (x >= min(x1, x2) - 1e-6 && x <= max(x1, x2) + 1e-6 && x >= min(x3, x4) - 1e-6 && x <= max(x3, x4) + 1e-6) {
  120.                 return new Point(x, a12 * x + b12);
  121.             } else {
  122.                 return null;
  123.             }
  124.         }
  125.  
  126.         boolean closeToZero(double v) {
  127.             // Check if double is close to zero, considering precision issues.
  128.             return Math.abs(v) <= 0.0000000000001;
  129.         }
  130.     }
  131.  
  132.     static class Point {
  133.         double x, y;
  134.  
  135.         public Point(double x, double y) {
  136.             this.x = x;
  137.             this.y = y;
  138.         }
  139.  
  140.         @Override
  141.         public String toString() {
  142.             return "(" + x + ", " + y + ")";
  143.         }
  144.     }
  145.  
  146.     public static void main(String[] args) throws IOException {
  147.  
  148.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1024 * 1024 * 2);
  149.  
  150.         int[] v = readArrayLine(br.readLine(), 6);
  151.         int m = v[0], n = v[1];
  152.         double w = v[2], speed = v[3];
  153.         int lx = v[4] - 1, ly = v[5] - 1;
  154.  
  155.         Building[][] b = new Building[n][m];
  156.  
  157.         int currentX;
  158.         int currentY = 0;
  159.         for (int i = 0; i < n; i++) {
  160.             v = readArrayLine(br.readLine(), m);
  161.             currentX = 0;
  162.             for (int j = 0; j < m; j++) {
  163.                 b[i][j] = new Building(currentX, currentY, v[j], i, j);
  164.                 currentX += w;
  165.             }
  166.             currentY += w;
  167.         }
  168.  
  169. //        Segment[] horizontal = new Segment[n - 1];
  170. //        Segment[] vertical = new Segment[m - 1];
  171. //        for (int i = 0; i < n - 1; i++) {
  172. //            double hy = w / 2 + w * i;
  173. //            horizontal[i] = new Segment(0, hy, w * (n - 1), hy);
  174. //        }
  175. //
  176. //        for (int i = 0; i < m - 1; i++) {
  177. //            double vx = w / 2 + w * i;
  178. //            vertical[i] = new Segment(vx, 0, vx, w * (m - 1));
  179. //        }
  180.  
  181.         Building root = b[ly][lx];
  182.         LinkedList<Building> queue = new LinkedList<>();
  183.         queue.add(root);
  184.         root.visited = true;
  185.  
  186.         while (!queue.isEmpty()) {
  187.             root = queue.poll();
  188.  
  189.             if (root == null) {
  190.                 break;
  191.             }
  192.  
  193.             for (int i = 0; i < n; i++) {
  194.                 for (int j = 0; j < m; j++) {
  195.                     Building dest = b[i][j];
  196.                     if (dest.visited) {
  197.                         continue;
  198.                     }
  199.  
  200. //                    if (canJump(root, dest, speed, vertical, horizontal, w, b)) {
  201.                     if (canJumpSmart(root, dest, speed, w, b)) {
  202.                         dest.steps = root.steps + 1;
  203.                         dest.visited = true;
  204.                         queue.add(dest);
  205.                     }
  206.                 }
  207.             }
  208.         }
  209.  
  210.         for (int i = 0; i < n; i++) {
  211.             for (int j = 0; j < m; j++) {
  212.                 if (b[i][j].steps == 0 && (i != ly || j != lx)) {
  213.                     System.out.print("X ");
  214.                 } else {
  215.                     System.out.print(b[i][j].steps + " ");
  216.                 }
  217.             }
  218.             System.out.println();
  219.         }
  220.     }
  221.  
  222.  
  223. //    private static boolean canJump(Building root, Building dest, double speed, Segment[] vertical, Segment[] horizontal, double w, Building b[][]) {
  224. //        double dist = getHorizontalDistBetweenSquared(root, dest);
  225. //        int heightDiff = dest.z - root.z;
  226. //
  227. //        double launchAngle = getAngle(speed, Math.sqrt(dist), heightDiff);
  228. //        if (launchAngle > 0) {
  229. //            return checkTrajectory(b, speed, root, dest, Math.tan(launchAngle), vertical, horizontal, w);
  230. //        }
  231. //        return false;
  232. //    }
  233.  
  234.     private static boolean canJumpSmart(Building root, Building dest, double speed, double w, Building b[][]) {
  235.         double dist = getHorizontalDistBetweenSquared(root, dest);
  236.         int heightDiff = dest.z - root.z;
  237.  
  238.         double tangentOfLaunchAngle = getTangentOfLaunchAngle(speed, Math.sqrt(dist), heightDiff, 1);
  239.         double tangentOfLaunchAngle1 = getTangentOfLaunchAngle(speed, Math.sqrt(dist), heightDiff, -1);
  240.  
  241.         boolean check1 = false;
  242.         if (tangentOfLaunchAngle > 0) {
  243.             check1 = checkTrajectorySimple(b, speed, root, dest,tangentOfLaunchAngle, w);
  244.         }
  245.  
  246.         boolean check2 = false;
  247.         if (tangentOfLaunchAngle1 > 0) {
  248.             check2 = checkTrajectorySimple(b, speed, root, dest, tangentOfLaunchAngle1, w);
  249.         }
  250.         return check1 || check2;
  251.     }
  252.  
  253.     private static boolean isAboveBuilding(Building b, double speed, double tangentOfLaunchAngle, Point intersection, int h0) {
  254.         double xDist = b.x - intersection.x;
  255.         double yDist = b.y - intersection.y;
  256.         double dist = Math.sqrt(xDist * xDist + yDist * yDist);
  257.         double computedHeight = computeHeightForDistAndTan(h0, speed, tangentOfLaunchAngle, dist);
  258.         return computedHeight >= b.z - 1e-9;
  259.     }
  260.  
  261.     private static boolean checkTrajectorySimple(Building[][] b, double speed, Building root, Building dest, double tan, double w) {
  262.         Segment s = new Segment(root.x, root.y, dest.x, dest.y);
  263.         int h0 = root.z;
  264.         for (int i = 0; i < b.length ; i ++) {
  265.             for (int j = 0 ; j < b[i].length ; j++) {
  266.                 double x = b[i][j].x;
  267.                 double y = b[i][j].y;
  268.                 List<Point> polygon = new ArrayList<>();
  269.                 polygon.add(new Point(x - w/2, y - w/2));
  270.                 polygon.add(new Point(x + w/2, y - w/2));
  271.                 polygon.add(new Point(x + w/2, y + w/2));
  272.                 polygon.add(new Point(x - w/2, y + w/2));
  273.  
  274.                 Point intersect = null;
  275.                 for (int k = 0 ; k < 4 ; k ++) {
  276.                     Point p1 = polygon.get(k);
  277.                     Point p2 = polygon.get((k+1)%polygon.size());
  278.                     Segment polySeg = new Segment(p1.x, p1.y, p2.x, p2.y);
  279.                     intersect = s.intersect(polySeg);
  280.                     boolean inter = Line2D.linesIntersect(p1.x, p1.y, p2.x, p2.y, s.x1, s.y1, s.x2, s.y2);
  281.                     if (intersect != null && intersect != Segment.OVERLAP) {
  282.                         if (!inter) {
  283.                             throw null;
  284.                         }
  285.                         if (!isAboveBuilding(b[i][j], speed, tan, intersect, h0)) {
  286.                             return false;
  287.                         }
  288.                     } else {
  289.                         if (inter) {
  290. //                            System.out.println(s + " " + polySeg + " "  + intersect);
  291.                             throw null;
  292.                         }
  293.                     }
  294.                 }
  295.             }
  296.         }
  297.  
  298.         return true;
  299.     }
  300.  
  301. //    private static boolean checkTrajectory(Building[][] b, double speed, Building root, Building dest, double tan, Segment[] verticals, Segment[] horizontals, double w) {
  302. //
  303. //        Segment s = new Segment(root.x, root.y, dest.x, dest.y);
  304. //        Map<Segment, Point> segmentPointMap = new HashMap<>();
  305. //        int h0 = root.z;
  306. //        for (int i = 0; i < horizontals.length; i++) {
  307. //            Segment segment = horizontals[i];
  308. //            Point intersect = s.intersect(segment);
  309. //            if (intersect != null && intersect != Segment.OVERLAP) {
  310. ////                System.out.println(intersect + " = " + ("[" + root.i + ", " + root.j + "]") + " " + ("[" + dest.i + ", " + dest.j + "]") + " ----> " + segment);
  311. //                segmentPointMap.put(segment, intersect);
  312. //                if (verticals.length > 0) {
  313. //                    if (intersect.x >= verticals[0].x1 - w && intersect.x <= verticals[0].x1) {
  314. ////                        System.out.println(("-> [" + i + ", " + 0 + "]") + " " + ("[" + (i + 1) + ", " + 0 + "]"));
  315. //                        if (!isAboveBuilding(b[i][0], speed, tan, intersect, h0)
  316. //                                || !isAboveBuilding(b[i + 1][0], speed, tan, intersect, h0)) {
  317. //                            return false;
  318. //                        }
  319. //                    }
  320. //                    for (int j = 0; j < verticals.length; j++) {
  321. //                        if (intersect.x >= verticals[j].x1 && intersect.x <= verticals[j].x1 + w) {
  322. ////                            System.out.println(("-> [" + i + ", " + (j + 1) + "]") + " " + ("[" + (i + 1) + ", " + (j + 1) + "]"));
  323. //                            if (!isAboveBuilding(b[i][j + 1], speed, tan, intersect, h0)
  324. //                                    || !isAboveBuilding(b[i + 1][j + 1], speed, tan, intersect, h0)) {
  325. //                                return false;
  326. //                            }
  327. //                        }
  328. //                    }
  329. //                } else {
  330. ////                    System.out.println(("-> [" + i + ", " + 0 + "]") + " " + ("[" + (i + 1) + ", " + 0 + "]"));
  331. //                    if (!isAboveBuilding(b[i][0], speed, tan, intersect, h0)
  332. //                            || !isAboveBuilding(b[i + 1][0], speed, tan, intersect, h0)) {
  333. //                        return false;
  334. //                    }
  335. //                }
  336. //            }
  337. //        }
  338. //
  339. //        for (int i = 0; i < verticals.length; i++) {
  340. //            Segment segment = verticals[i];
  341. //            Point intersect = s.intersect(segment);
  342. //            if (intersect != null && intersect != Segment.OVERLAP) {
  343. ////                System.out.println(intersect + " = " + ("[" + root.i + ", " + root.j + "]") + " " + ("[" + dest.i + ", " + dest.j + "]") + " ----> " + segment);
  344. //                segmentPointMap.put(segment, intersect);
  345. //                if (horizontals.length > 0) {
  346. //                    if (intersect.y >= horizontals[0].y1 - w && intersect.y <= horizontals[0].y1) {
  347. ////                        System.out.println(("-< [" + 0 + ", " + i + "]") + " " + ("[" + 0 + ", " + (i + 1) + "]"));
  348. //                        if (!isAboveBuilding(b[0][i], speed, tan, intersect, h0)
  349. //                                || !isAboveBuilding(b[0][i + 1], speed, tan, intersect, h0)) {
  350. //                            return false;
  351. //                        }
  352. //                    }
  353. //                    for (int j = 0; j < horizontals.length; j++) {
  354. //                        if (intersect.y >= horizontals[j].y1 && intersect.y <= horizontals[j].y1 + w) {
  355. ////                            System.out.println(("-< [" + (j + 1) + ", " + i + "]") + " " + ("[" + (j + 1) + ", " + (i + 1) + "]"));
  356. //                            if (!isAboveBuilding(b[j + 1][i], speed, tan, intersect, h0)
  357. //                                    || !isAboveBuilding(b[j + 1][i + 1], speed, tan, intersect, h0)) {
  358. //                                return false;
  359. //                            }
  360. //                        }
  361. //                    }
  362. //                } else {
  363. ////                    System.out.println(("-< [" + 0 + ", " + i + "]") + " " + ("[" + 0 + ", " + (i + 1) + "]"));
  364. //                    if (!isAboveBuilding(b[0][i], speed, tan, intersect, h0)
  365. //                            || !isAboveBuilding(b[0][i + 1], speed, tan, intersect, h0)) {
  366. //                        return false;
  367. //                    }
  368. //                }
  369. //            }
  370. //        }
  371. //
  372. ////        System.out.println("end for " + ("[" + root.i + ", " + root.j + "]") + " " + ("[" + dest.i + ", " + dest.j + "]"));
  373. ////        System.out.println();
  374. //        return true;
  375. //    }
  376.  
  377.     private static double getHorizontalDistBetweenSquared(Building b1, Building b2) {
  378.         return (b1.x - b2.x) * (b1.x - b2.x) + (b1.y - b2.y) * (b1.y - b2.y);
  379.     }
  380.  
  381.     private static double getTangentOfLaunchAngle(double speed, double dist, double h, int coef) {
  382.         double a = G * dist * dist / (2 * speed * speed);
  383.         double b = -dist;
  384.         double c = a + h;
  385.  
  386.         double delta = b * b - 4 * a * c;
  387.  
  388.         if (delta < 0) {
  389.             return -1;
  390.         }
  391.  
  392.         return (-b + coef * Math.sqrt(delta)) / (2 * a);
  393.     }
  394.  
  395.     private static double getAngle(double v, double dist, double h) {
  396.         double start = Math.PI / 2;
  397.         double end = Math.PI / 4;
  398.         double computedY = Double.MAX_VALUE;
  399.         double x = 0;
  400.  
  401.         while (Math.abs(computedY - h) > 0.000005) {
  402.             x = (start + end) / 2;
  403.             if (start == x || end == x) {
  404.                 return -1;
  405.             }
  406.  
  407.             double vy = v * Math.sin(x);
  408.             double timeToHighest = vy / G;
  409.             double vx = v * Math.cos(x);
  410.             double timeToDist = dist / vx;
  411.  
  412.             if (timeToDist < timeToHighest - 1e-9) {
  413.                 end = x;
  414.                 continue;
  415.             }
  416.  
  417.             computedY = computeHeightForDistAndTan(0, v, Math.tan(x), dist);
  418.             if (start - end < 0.00000000000000000000001) {
  419.                 return -1;
  420.             }
  421.             if (computedY < h) {
  422.                 start = x;
  423.             } else {
  424.                 end = x;
  425.             }
  426.         }
  427.         return x;
  428.     }
  429.  
  430.     private static double computeHeightForDistAndTan(int h0, double speed, double tan, double dist) {
  431.         return h0 + dist * tan - G * dist * dist * (1 + tan * tan) / (2 * speed * speed);
  432.     }
  433.  
  434.     public static int[] readArrayLine(String line, int n) {
  435.         return readArrayLine(line, n, null, 0);
  436.     }
  437.  
  438.     private static int[] readArrayLine(String line, int n, int array[], int pos) {
  439.         int[] ret = array == null ? new int[n] : array;
  440.         int start = 0;
  441.         int end = line.indexOf(' ', start);
  442.         for (int i = pos; i < pos + n; i++) {
  443.             if (end > 0)
  444.                 ret[i] = Integer.parseInt(line.substring(start, end));
  445.             else
  446.                 ret[i] = Integer.parseInt(line.substring(start));
  447.             start = end + 1;
  448.             end = line.indexOf(' ', start);
  449.         }
  450.         return ret;
  451.     }
  452. }
  453.  
Runtime error #stdin #stdout #stderr 0.08s 2184192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.NullPointerException
	at Main.readArrayLine(Main.java:441)
	at Main.readArrayLine(Main.java:435)
	at Main.main(Main.java:150)
https://ideone.com/IpZBm8
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!