Advertisement
Guest User

Untitled

a guest
May 8th, 2018
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.21 KB | None | 0 0
  1. package _04_dynamic_programming.lab;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.IOException;
  5. import java.io.InputStreamReader;
  6. import java.nio.charset.StandardCharsets;
  7. import java.util.*;
  8.  
  9. public class Pr03Lumber2 {
  10.  
  11.     public static void main(final String[] args) {
  12.  
  13.         try (final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in, StandardCharsets.UTF_8))) {
  14.             // Stream - 0.160+ sec.
  15. /*            int[] tokens2 = Arrays.stream(reader.readLine().split("\\s+"))
  16.                     .mapToInt(Integer::valueOf)
  17.                     .toArray();
  18.  
  19.             int logsCount = tokens2[0];
  20.             int queries = tokens2[1];
  21.             String[] tokens;*/
  22.  
  23.             // "Manual" parsing - 0.08 - 0.1 sec.
  24.             String[] tokens = reader.readLine().split("\\s+");
  25.  
  26.             int logsCount = Integer.parseInt(tokens[0]);
  27.             int queries = Integer.parseInt(tokens[1]);
  28.  
  29.             ///////////////////
  30.             Log[] logs = new Log[logsCount + 1];
  31.  
  32.             for (int root = 1; root <= logsCount; root++) {
  33.                 tokens = reader.readLine().split("\\s+");
  34.                 int x1 = Integer.parseInt(tokens[0]);
  35.                 int y1 = Integer.parseInt(tokens[1]);
  36.                 int x2 = Integer.parseInt(tokens[2]);
  37.                 int y2 = Integer.parseInt(tokens[3]);
  38.  
  39.                 Log currentLog = new Log(x1, y1, x2, y2, root);
  40.  
  41.                 logs[root] = currentLog;
  42.  
  43.                 Set<Integer> toRedirect = new HashSet<>();
  44.                 for (int j = 1; j < root; j++) {
  45.                     if (!logs[j].isOverlapping(currentLog)) {
  46.                         continue;
  47.                     }
  48.  
  49.                     toRedirect.add(logs[j].root);
  50.                 }
  51.  
  52.                 for (int j = 1; j < root; j++) {
  53.                     if (toRedirect.contains(logs[j].root)) {
  54.                         logs[j].root = root;
  55.                     }
  56.                 }
  57.             }
  58.  
  59.             final StringBuilder sb = new StringBuilder();
  60.  
  61.             for (int i = 0; i < queries; i++) {
  62.                 tokens = reader.readLine().split("\\s+");
  63.                 int id1 = Integer.parseInt(tokens[0]);
  64.                 int id2 = Integer.parseInt(tokens[1]);
  65.  
  66.                 sb.append(logs[id1].isConnected(logs[id2]) ? "YES" : "NO").append(System.lineSeparator());
  67.             }
  68.  
  69.             System.out.println(sb.toString());
  70.         } catch (IOException | NullPointerException e) {
  71.             e.printStackTrace();
  72.         }
  73.     }
  74.  
  75.     private static class Log {
  76.         private int root;
  77.         private int x1;
  78.         private int y1;
  79.         private int x2;
  80.         private int y2;
  81.  
  82.         Log(int x1, int y1, int x2, int y2, int root) {
  83.             this.x1 = x1;
  84.             this.y1 = y1;
  85.             this.x2 = x2;
  86.             this.y2 = y2;
  87.             this.root = root;
  88.         }
  89.  
  90.         boolean isOverlapping(Log other) {
  91.             return this.x1 <= other.x2 &&
  92.                     other.x1 <= this.x2 &&
  93.                     this.y1 >= other.y2 &&
  94.                     other.y1 >= this.y2;
  95.         }
  96.  
  97.         boolean isConnected(Log other) {
  98.             return this.root == other.root;
  99.         }
  100.     }
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement