Metro
Национална Олимпиада по Информатика 2013, Контролно 2
Time Limit: 0.5s, Memory Limit: 64MiB
След 42 години разработка на операционни системи, през 2012-та се стигна до кулминацията в този процес с нещо напълно иновативно - правоъгълници! Фирмата Малкомек разработиха техния Метро дизайн, който показва прозорците на екрана като цветни правоъгълници със страни, успоредни на страните на дисплея. За да се виждат всички прозорци, тяхната операционна система не разрешава два прозореца да се пресичат, освен ако единият не се съдържа изцяло в другия (без краищата им да се допират). По-малките прозорци са винаги по-отгоре, което позволява всички те да се виждат.

Фирмата Малкомек има славата да иска пари от потребителите си за какво ли не. Заедно с нечуваната иновация в графичния дизайн (правоъгълниците), те въведоха и нов начин за заплащане при ползване на техния продукт. Вместо да се плаща за инсталирането му, потребителите заплащат всеки път, когато курсорът на мишката им премине през ръб на прозорец. Разбира се, сега потребителите много внимават къде движат мишката си, за да плащат възможно най-малко.

Например ако на екрана има един единствен малък прозорец в средата на екрана и потребителят иска да стигне с мишката от долния ляв ъгъл до горния десен такъв, той ще трябва да заплати две пресичания на стена, ако реши да прекара мишката по диагонала. За сметка на това, той може да "заобиколи" прозореца и да не заплати нито едно. Ако иска да стигне от ъгъла до центъра на екрана, обаче, той няма избор освен да мине веднъж през стена на прозореца и да заплати едно минаване.

Ели реши да направи софтуерен продукт, който по зададено разположенито на прозорците отговаря бързо на въпроси "колко е минималната цена за предвижване на курсора от точка (SX, SY) до точка (EX, EY)", където (SX, SY) и (EX, EY) са точки, задаващи пиксели на екрана. В задачата, долният ляв ъгъл на монитора е с координати (0, 0), а горният десен – с координати (1,000,000, 1,000,000). Тя много искаше сама да напише продукта, но за нещастие се наложи да отиде на Канарските острови за една седмица с парите, дадени й за разработката му, като сега частта с писането му се пада на вас.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло положително число N – броя на прозорците. Следват N реда, всеки от които съдържа по четири неотрицателни цели числа DXi, DYi, UXi, и UYi. Те представляват две координати на екрана (DXi, DYi) и (UXi, UYi), задаващи, съответно, координатите на долния ляв и горния десен ъгъл на прозореца.

На следващия ред е зададено цялото положително число Q – броя въпроси, които вашата програма трябва да обработи. Следват Q реда, всеки от които съдържа по четири неотрицателни цели числа SXi, SYi, EXi, EYi. Те представляват две координати на екрана (SXi, SYi) и (EXi, EYi), задаващи, съответно, началната и крайната позиция на курсора за съответния въпрос.
Изход
За всеки въпрос на отделен ред изпечатайте по едно цяло неотрицателно число – минималния брой стени на прозорци, през които трябва да мине курсорът за да стигне от началната до крайната точка. За простота считаме преминаването през ъгъл на прозорец за преминаване през една стена.
Ограничения
  • 1 ≤ N, Q ≤ 100,000
  • 0 ≤ DXi < UXi ≤ 1,000,000
  • 0 ≤ DYi < UYi ≤ 1,000,000
  • 0 ≤ SXi, SYi, EXi, EYi ≤ 1,000,000
  • Между всеки две стени на прозорци има поне един пиксел разстояние (достатъчно за да може потребителят да мине с курсора оттам).
  • Началните и крайните точки на курсора във всеки от въпросите не лежи на стена на прозорец.
Примерен Вход Примерен Изход
7 0 4 2 26 8 8 18 20 10 10 12 14 6 6 30 24 14 16 16 18 22 10 28 14 22 18 28 22 9 15 1 13 27 1 7 1 5 1 7 21 17 17 31 11 11 11 11 15 17 9 11 29 11 9 11 27 11 1 23 15 17 29 23 7 7 0 0 2 3 2 1 2 4 0
Обяснение на примерния вход и изход.
Мрън!