Ограничение памяти: 64 М байт. На ежегодную выставку достижений в области информатике приехало множество фирм –

На ежегодную выставку достижений в области информатике приехало множество фирм – производителей программной продукции. Организаторы выставки отвели каждой фирме место в выставочном зале согласно её потребностям. Однако не была учтена одна очень важная деталь. Одни фирмы разрабатывают программы для операционной системы “Doors”, другие же – для операционной системы “Panix”. Причём отношения между представителями фирм, пользующихся разными операционными системами, оказались настолько плохими, что, находясь в пределах прямой видимости, они тут же начинали ссориться и даже драться. Необходимо было срочно принимать какие-то меры. Организаторы выставки решили разделить выставочный зал сплошной стеной так, чтобы все пользователи “Doors” оказались по одну сторону, а все пользователи “Panix” – по другую. При этом стена не должна иметь никаких изгибов (то есть основание стены есть отрезок прямой линии), и, конечно, экспозиции фирм не могут перемещаться. Экспозиция любой фирмы занимает прямоугольный участок выставочного зала. Стороны прямоугольников параллельны координатным осям. Прямоугольники не пересекаются и не касаются друг друга.

Напишите программу, которая определяет, можно ли соорудить такую стену.

Вход

В первой строке входного файла записано два целых числа D и P – количество фирм, работающих в системе “Doors” и количество фирм, работающих в системе “Panix” (1 ≤ D, P ≤ 500). Следующие D строк содержат описание экспозиций пользователей “Doors”. В оставшихся P строках содержится описание экспозиций пользователей “Panix”. Каждая экспозиция задаётся четырьмя целыми числами x₁, y₁, x₂, y₂. (x₁, y₁) – координаты юго-западного угла прямоугольника, а (x₂, y₂) – координаты северо-восточного угла (0 < x₁ < x₂ <15000, 0 < y₁ < y₂ < 15000).

Выход

Запишите в выходной файл слово “Yes”, если стену можно соорудить, и слово “No” в противном случае.

Пример входа и выхода

Запдача 8. Aerodynamics

Input file: aerodynamics.in

Output file: aerodynamics.out

Time Limit: 1 second

Memory Limit: 64M byte

Bill is working in a secret laboratory. He is developing missiles for national security projects. Bill is the head of the aerodynamics department. One surprising fact of aerodynamics is called Whitcomb area rule. An object flying at high-subsonic speeds develops local supersonic airflows and the resulting shock waves create the effect called wave drag. Wave drag does not depend on the exact form of the object, but rather on its cross-sectional profile. Consider a coordinate system with OZ axis pointing in the direction of object's motion. Denote the area of a section of the object by a plane z = z₀ as S(z₀). Cross-sectional profile of the object is a function S that maps z₀ to S(z₀). There is a perfect aerodynamic shape called Sears-Haack body. The closer cross-sectional profile of an object to the cross-sectional profile of Sears-Haack body, the less wave drag it introduces. That is an essence of Whitcomb area rule. Bill's department makes a lot of computer simulations to study missile's aerodynamic properties before it is even built. To approximate missile's cross-sectional profile one takes samples of S(z₀) for integer arguments z₀ from z_min to z_max.

Your task is to find the area S(z₀) for each integer z₀ from z_min to z_max, inclusive, given the description of the missile. The description of the missile is given to you as a set of points. The missile is the minimal convex solid containing all the given points. It is guaranteed that there are four points that do not belong to the same plane.

Input

The first line of the input _le contains three integer numbers: n, z_min and z_max (4 ≤ n ≤ 100, 0 ≤ z_min ≤ z_max ≤ 100). The following n lines contain three integer numbers each: x, y, and z coordinates of the given points. All coordinates do not exceed 100 by their absolute values. No two points coincide. There are four points that do not belong to the same plane.

Output

For each integer z₀ from z_min to z₀, inclusive, output one floating point number: the area S(z₀). The area must be precise to at least 5 digits after decimal point.

Поиск по сайту: