Задача . Tree Boxes

ФД рассматривает ферму как точку на 2-мерной плоскости. Он хотел бы получать информацию о проблемах на одной из ферм в прямоугольных координатах. А именно он хочет получать информацию в виде не более двух прямоугольников, параллельных осям координат, чьё пересечение пустое, а объединение содержит все фермы на пути от \(A\) к \(B\). Вы должны помочь ФД определить, как расположить его фермы так, чтобы условие выполнялось.

Это интерактивная задача. Вы не должны использовать ввод-вывод. Решения, использующие ввод-вывод будут дисквалифицированы. Но Вам разрешено использовать глобальные и статические переменные. Вы должны разработать следующие функции:

• void addRoad(int A, int B): обрабатывает дорогу между фермами \(A\) и \(B\) (\(0 \le A, B \le N - 1\)).
• void buildFarms(): Определяет, где ФД должен построить все свои фермы.
• void notifyFJ(int A, int B): сообщает ФД один или два прямоугольника, которые удовлетворяют вышеописанным условиям

Ваша реализация указанных выше функций должна вызывать следующие функции, перечисленные ниже. Вы можете полагать, что \(\texttt{notifyFJ}\) будет вызвана \(Q\) раз.

• int getN(): получить значение \(N\).
• int getQ(): получить значение \(Q\).
• void setFarmLocation(int ID, int X, int Y): определяет, что ФД должен построить ферму с номером \(ID\) (\(0 \le ID \le N-1\)) в позиции \((X,Y)\), где \((1 \le X, Y \le 10^5 )\). Она будет вызвана из \(\texttt{buildFarms}\).
• void addBox(int X1, int Y1, int X2, int Y2): добавляет прямоугольник для сообщения ФД, \((1 \le X1 \le X2 \le 10^5 )\) и \((1 \le Y1 \le Y2 \le 10^5 )\). Вызывается только из \(\texttt{notifyFJ}\).

Интерактивный протокол работает следующим образом: Сначала \(\texttt{addRoad}\) вызывается \(N-1\) раз, чтобы информировать Вашу программу о системе дорог. Затем, будет вызвана \(\texttt{buildFarms}\) и Вы должны будете определить, где ФД должен построить каждую свою ферму соотвественно. А потом будут \(Q\) вызовов \(\texttt{notifyFJ}\) где Вы должны будете сделать один или два вызова \(\texttt{addBox}\) для нотификации ФД.

Гарантируется, что всегда существует корректный способ нотифицировать ФД одним или двумя прямоугольниками. Ограничение по памяти для данной задачи 512 Мбт (в отличие от обычных 256).

Для C++ решений, используйте такой template:

#include "grader.h"

void addRoad(int a, int b){
	// Fill in code here
}

void buildFarms(){
	// Fill in code here
}

void notifyFJ(int a, int b){
	// Fill in code here
}

Для Java решений, исполозуйте такой template:

import java.io.IOException;
// If you find it necessary, you may import other standard libraries here.
public class boxes extends Grader {

  	// Copy this exactly:
        
Override
  	public static void main(String args[]) throws IOException { new boxes().run(); }

        
Override
  	public void addRoad(int a, int b) {
      // Fill in code here
  	}
        
Override
  	public void buildFarms(){
      // Fill in code here
	  }
  	
Override
  	public void notifyFJ(int a, int b){
      // Fill in code here
  	}
}
}

Пример взаимодействия

Grader calls \(\texttt{addRoad(0,1)}\)

Grader calls \(\texttt{addRoad(1,2)}\)

Grader calls \(\texttt{buildFarms()}\)

Solution calls \(\texttt{setFarmLocation(0,1,1)}\)

Solution calls \(\texttt{setFarmLocation(1,1,2)}\)

Solution calls \(\texttt{setFarmLocation(2,2,2)}\)

Solution ends \(\texttt{buildFarms()}\)

Grader calls \(\texttt{notifyFJ(0,0)}\)

Solution calls \(\texttt{addBox(1,1,1,1)}\)

Solution ends \(\texttt{notifyFJ(0,0)}\)

Grader calls \(\texttt{notifyFJ(0,2)}\)

Solution calls \(\texttt{addBox(1,1,1,2)}\)

Solution calls \(\texttt{addBox(2,2,2,2)}\)

Solution ends \(\texttt{notifyFJ(0,2)}\)

Грайдер завершает свою работу, решение прошло тест.

Автор: Spencer Compton