Фермер Джон планирует построить \(N\) (\(1 \leq N \leq 10^5\)) ферм, которые будут
соединены \(N-1\) дорожками, образовывая дерево. Обычно когда на одной из ферм
возникает проблема, он получает информацию в виде " имеется проблема на одной
из ферм на пути от фермы \(A\) к ферме \(B\).
ФД рассматривает ферму как точку на 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