Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package SoftUniada2017;
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.*;
- public class Pr07Lumber {
- public static void main(String[] args) throws IOException {
- BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
- String[] input = reader.readLine().split(" ");
- int recN = Integer.parseInt(input[0]);
- int queryN = Integer.parseInt(input[1]);
- boolean[][] noRootTo = new boolean[recN][recN];
- List<Rectangle> logs = new ArrayList<>();
- for (int i = 0; i < recN; i++) {
- input = reader.readLine().split(" ");
- int x1 = Integer.parseInt(input[0]);
- int y1 = Integer.parseInt(input[1]);
- int x2 = Integer.parseInt(input[2]);
- int y2 = Integer.parseInt(input[3]);
- Rectangle log = new Rectangle(recN, i, x1, y1, x2, y2);
- for (Rectangle oldLog : logs) {
- log.intersects(oldLog);
- }
- logs.add(log);
- }
- StringBuilder output = new StringBuilder();
- for (int i = 0; i < queryN; i++) {
- input = reader.readLine().split(" ");
- int id1 = Integer.parseInt(input[0]) - 1;
- int id2 = Integer.parseInt(input[1]) - 1;
- if (id1 == id2) {
- output.append("YES").append(System.lineSeparator());
- continue;
- }
- if(noRootTo[id1][id2] || noRootTo[id2][id1]) {
- output.append("NO").append(System.lineSeparator());
- continue;
- }
- Rectangle log1 = logs.get(id1);
- Rectangle log2 = logs.get(id2);
- if (log1.hasRoutTo(log2)) {
- output.append("YES").append(System.lineSeparator());
- } else {
- noRootTo[log1.id][log2.id] = true;
- output.append("NO").append(System.lineSeparator());
- }
- }
- System.out.print(output);
- }
- }
- class Rectangle {
- int id;
- private int x1;
- private int y1;
- private int x2;
- private int y2;
- private List<Rectangle> intersectsWith;
- private int amountOfRecs;
- private int group;
- Rectangle(int amountOfRecs, int id, int x1, int y1, int x2, int y2) {
- this.id = id;
- this.amountOfRecs = amountOfRecs;
- this.intersectsWith = new ArrayList<>();
- this.group = -1;
- if (x1 < x2) {
- this.x1 = x1;
- this.x2 = x2;
- } else {
- this.x1 = x2;
- this.x2 = x1;
- }
- if (y1 < y2) {
- this.y1 = y1;
- this.y2 = y2;
- } else {
- this.y1 = y2;
- this.y2 = y1;
- }
- }
- boolean intersects(Rectangle other) {
- if (this.x1 <= other.x2 && this.x2 >= other.x1 &&
- this.y1 <= other.y2 && this.y2 >= other.y1) {
- this.intersectsWith.add(other);
- other.intersectsWith.add(this);
- return true;
- } else {
- return false;
- }
- }
- boolean hasRoutTo(Rectangle other) {
- boolean result = false;
- if(this.group != -1 && this.group == other.group) {
- return true;
- }
- Queue<Rectangle> queue = new ArrayDeque<>();
- boolean[] visited = new boolean[this.amountOfRecs];
- queue.add(this);
- visited[this.id] = true;
- this.group = this.id;
- while (queue.size() > 0) {
- Rectangle currNode = queue.poll();
- for (Rectangle neighbourNode : currNode.intersectsWith) {
- neighbourNode.group = this.group;
- if(neighbourNode.id == other.id) {
- result = true;
- }
- if (!visited[neighbourNode.id]) {
- queue.add(neighbourNode);
- visited[neighbourNode.id] = true;
- }
- }
- }
- return result;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement