1. Мотель (100 балів)

Максимальна оцінка: 100 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: motel.in
Вихідний файл: motel.out
Програма: motel.*

Рiвнину перетинають прямолінійні швидкiснi автостради.

Завдання
Створiть програму motel.*, яка вибере найвигiднiше мiсце для мотелю, вiд якого сума вiдстаней до всiх автострад найменша.

Вхідні дані
Перший рядок вхiдного файлу motel.in мiстить натуральне число n — кiлькiсть автострад, якi надалi вважаємо рiзними прямими лiнiями.

Для j в межах вiд 1 до n включно (j + 1)-ий рядок цього файлу мiстить 4 натуральних числа — декартовi координати двох рiзних точок на j-iй прямiй, вiдстань мiж якими виражається натуральним числом. Ці 4 числа подано у такому порядку: спочатку абсциса й ордината однієї точки, потім — абсциса й ордината іншої точки.

Кiлькiсть прямих n лежить в межах вiд 2 до 10, а всi iншi числа вхiдного файлу motel.in не перевищують 123.

Вихідні дані
Перший рядок вихiдного файлу motel.out має мiстити найменшу можливу суму вiдстаней вiд автострад до мотелю. Наступні рядки мають такий вигляд.

1. Якщо шукана множина містить лише одну точку, то:
   • другий рядок вихідного файлу має містити число 1;
   • третій рядок вихідного файлу має мiстити координати цієї точки.
2. Якщо шукана множина є відрізком, то:
   • другий рядок вихідного файлу має містити число 2;
   • третій рядок вихідного файлу має мiстити координати одного кінця цього відрізка;
   • четвертий рядок — координати іншого кінця цього відрізка.
3. Якщо шукана множина є опуклим n-кутником, то:
   • другий рядок вихідного файлу має містити число n;
   • рядки від третього до (n + 2)-го містять координати вершин цього многокутника (по дві координати однієї вершини в рядку).
4. Якщо шукана множина є однією з даних прямих, то:
   • другий рядок вихідного файлу має містити число –1;
   • третій рядок вихідного файлу має містити цілі коефіцієнти рівняння цієї прямої.
5. Якщо шукана множина частиною площини, розташованою між двома з даних прямих, то:
   • другий рядок вихідного файлу має містити число –2;
   • третій рядок вихідного файлу має містити цілі коефіцієнти рівняння однієї з цих прямих;
   • четвертий рядок — цілі коефіцієнти рівняння іншої прямої.

Занумеруємо дані прямі, координати точок яких подано вхідним файлом, у тому порядку, в якому їх подано вхідним файлом. У випадках 2–3 дані про вершини, що є точками перетину пари з даних прямих, потрібно розташувати у порядку неспадання меншого номера пари прямих, а при однакових менших номерах — у порядку зростання більшого номера. У випадку 5 коефіцієнти рівнянь прямих потрібно розташувати у порядку зростання номера прямої.

У випадках 1–3 координати точки потрібно записати у такому порядку:

• абсциса x;
• ордината y.

У випадках 4–5 коефіцієнти рівняння прямої потрібно записати у такому порядку:

• коефіцієнт при абсцисі x;
• коефіцієнт при ординаті y;
• вільний член.

Усі ці коефіцієнти мають бути цілими і найменшими за абсолютною величиною. Інакше кажучи, найбільший спільний дільник коефіцієнтів рівняння однієї прямої має дорівнювати 1. При цьому коефіцієнт при абсцисі має бути невід'ємним. Якщо він дорівнює нулю, то коефіцієнт при ординаті має бути додатним.

Будь-яке число у вiдповiдi треба подати нескоротним дробом з цiлим чисельником i натуральним знаменником, роздiленими знаком дiлення /. Якщо знаменник дорiвнює 1, то знак дiлення i знаменник не записувати.

Приклад

2. Тест (100 балів)

Максимальна оцінка: 100 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: test.in
Вихідний файл: test.out
Програма: test.*

У дитячому садку проводиться тестування. Дiтям показують бiлi аркушi паперу прямокутної форми, якi подiлено на рiвнi квадрати горизонтальними та вертикальними лiнiями. Частину квадратiв зафарбовано чорною фарбою, а частину нi.

Фiґурою на такому малюнку називають сукупнiсть чорних квадратiв, для довiльної пари яких центри квадратiв можна з'єднати ламаною, що повнiстю мiститься у чорних квадратах i не мiстить жодної вершини квадрата.

Рiзними фiґурами називають фiґури, якi неможливо сумiстити послiдовним застосуванням паралельних перенесень, поворотiв на 90° i симетрiї вiдносно вертикальної чи горизонтальної прямої.

Дiтям пропонують встановити, скiльки всього фiґур зображено на малюнку, i скiльки рiзних фiґур зображено на цьому малюнку.

Завдання
Створiть програму test.*, яка дає правильну вiдповiдь на поставлене питання.

Вхідні дані
Перший рядок вхiдного файлу test.in мiстить натуральне число n — кiлькість квадратiв, якi розташованi на малюнку по вертикалi та горизонталi.

Наступнi n рядкiв по n символiв цього файлу мiстять подання малюнку, в якому символ « » (пропуск) означає бiлий квадрат, а будь-який інший — чорний.

У 20% тестів n ≤ 30, у 40% тестів n ≤ 90, у 60% тестів n ≤ 180, у 80% тестів n ≤ 360, у всіх тестах n ≤ 528.

Кількість клітин однієї фіґури не перевищує: 50 у 20% тестів, 500 у 36% тестів, 2000 у 52% тестів, 8000 у 68% тестів, 15000 у 84% тестів, 125000 у 100% тестів.

Вихідні дані
Єдиний рядок вихiдного файлу test.out має мiстити у вказаному порядку два натуральних числа: кiлькiсть всiх фiґур та кiлькiсть рiзних фiґур. Вiдомо, що обидва шуканих числа не перевищують 248.

Приклад

9
***  **   
*   **    
*   *     
*   *     
          
  ** ***  
 **  *    
 *   *    
 *   *