Advertisement
Guest User

Untitled

a guest
Jan 11th, 2017
256
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.02 KB | None | 0 0
  1. package SoftUniada2017;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.IOException;
  5. import java.io.InputStreamReader;
  6. import java.util.*;
  7.  
  8. public class Pr07Lumber {
  9.  
  10.     public static void main(String[] args) throws IOException {
  11.         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  12.         String[] input = reader.readLine().split(" ");
  13.         int recN = Integer.parseInt(input[0]);
  14.         int queryN = Integer.parseInt(input[1]);
  15.         boolean[][] noRootTo = new boolean[recN][recN];
  16.         List<Rectangle> logs = new ArrayList<>();
  17.         for (int i = 0; i < recN; i++) {
  18.             input = reader.readLine().split(" ");
  19.             int x1 = Integer.parseInt(input[0]);
  20.             int y1 = Integer.parseInt(input[1]);
  21.             int x2 = Integer.parseInt(input[2]);
  22.             int y2 = Integer.parseInt(input[3]);
  23.             Rectangle log = new Rectangle(recN, i, x1, y1, x2, y2);
  24.             for (Rectangle oldLog : logs) {
  25.                 log.intersects(oldLog);
  26.             }
  27.             logs.add(log);
  28.         }
  29.         StringBuilder output = new StringBuilder();
  30.         for (int i = 0; i < queryN; i++) {
  31.             input = reader.readLine().split(" ");
  32.             int id1 = Integer.parseInt(input[0]) - 1;
  33.             int id2 = Integer.parseInt(input[1]) - 1;
  34.             if (id1 == id2) {
  35.                 output.append("YES").append(System.lineSeparator());
  36.                 continue;
  37.             }
  38.             if(noRootTo[id1][id2] || noRootTo[id2][id1]) {
  39.                 output.append("NO").append(System.lineSeparator());
  40.                 continue;
  41.             }
  42.             Rectangle log1 = logs.get(id1);
  43.             Rectangle log2 = logs.get(id2);
  44.             if (log1.hasRoutTo(log2)) {
  45.                 output.append("YES").append(System.lineSeparator());
  46.             } else {
  47.                 noRootTo[log1.id][log2.id] = true;
  48.                 output.append("NO").append(System.lineSeparator());
  49.             }
  50.         }
  51.         System.out.print(output);
  52.     }
  53. }
  54.  
  55. class Rectangle {
  56.  
  57.     int id;
  58.     private int x1;
  59.     private int y1;
  60.     private int x2;
  61.     private int y2;
  62.     private List<Rectangle> intersectsWith;
  63.     private int amountOfRecs;
  64.     private int group;
  65.  
  66.     Rectangle(int amountOfRecs, int id, int x1, int y1, int x2, int y2) {
  67.         this.id = id;
  68.         this.amountOfRecs = amountOfRecs;
  69.         this.intersectsWith = new ArrayList<>();
  70.         this.group = -1;
  71.         if (x1 < x2) {
  72.             this.x1 = x1;
  73.             this.x2 = x2;
  74.         } else {
  75.             this.x1 = x2;
  76.             this.x2 = x1;
  77.         }
  78.         if (y1 < y2) {
  79.             this.y1 = y1;
  80.             this.y2 = y2;
  81.         } else {
  82.             this.y1 = y2;
  83.             this.y2 = y1;
  84.         }
  85.     }
  86.  
  87.     boolean intersects(Rectangle other) {
  88.         if (this.x1 <= other.x2 && this.x2 >= other.x1 &&
  89.                 this.y1 <= other.y2 && this.y2 >= other.y1) {
  90.             this.intersectsWith.add(other);
  91.             other.intersectsWith.add(this);
  92.             return true;
  93.         } else {
  94.             return false;
  95.         }
  96.     }
  97.  
  98.     boolean hasRoutTo(Rectangle other) {
  99.         boolean result = false;
  100.         if(this.group != -1 && this.group == other.group) {
  101.             return true;
  102.         }
  103.         Queue<Rectangle> queue = new ArrayDeque<>();
  104.         boolean[] visited = new boolean[this.amountOfRecs];
  105.         queue.add(this);
  106.         visited[this.id] = true;
  107.         this.group = this.id;
  108.         while (queue.size() > 0) {
  109.             Rectangle currNode = queue.poll();
  110.             for (Rectangle neighbourNode : currNode.intersectsWith) {
  111.                 neighbourNode.group = this.group;
  112.                 if(neighbourNode.id == other.id) {
  113.                     result = true;
  114.                 }
  115.                 if (!visited[neighbourNode.id]) {
  116.                     queue.add(neighbourNode);
  117.                     visited[neighbourNode.id] = true;
  118.                 }
  119.             }
  120.         }
  121.         return result;
  122.     }
  123. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement