시야 (Line of Sight)

한 건축가가 새로 지은 집을 자랑스러워하며, 대지 경계선을 따라 난 길에서 이 집이 얼마나 잘 보이는지 알고 싶어 한다. 대지에는 나무, 관목, 울타리 등 시야를 가릴 수 있는 여러 장애물이 있다. 이 문제에서는 집, 경계선, 그리고 모든 장애물을 x축과 평행한 수평 선분으로 모델링한다.

집, 경계선, 장애물들의 위치가 주어질 때, 집 전체가 보이는 경계선의 연속 구간 중 가장 긴 구간의 길이를 구하는 프로그램을 작성하라. 경계선 위의 한 지점에서 집 전체가 보인다는 것은, 집 위의 모든 점에 대해 그 지점과 해당 점을 잇는 직선 선분이 어떤 장애물과도 교차하지 않음을 뜻한다.

모든 물체는 왼쪽 x좌표, 오른쪽 x좌표, y좌표로 표현되는 수평 선분이다.

x1 x2 y

여기서 x1, x2, y는 음이 아닌 실수이며 x1 < x2이다.

하나의 입력에는 여러 채의 집이 담길 수 있다. 각 집에 대해:

• 첫 번째 줄에는 집 선분이 주어진다.
• 두 번째 줄에는 경계선 선분이 주어진다.
• 세 번째 줄에는 장애물의 개수를 나타내는 정수 하나가 주어진다.
• 이어지는 각 줄에는 장애물 선분이 하나씩 주어진다.

마지막 집 다음에 오는 0 0 0 줄이 입력의 끝을 나타낸다.

모든 집은 자신의 경계선보다 항상 위에 있다(집의 y > 경계선의 y). 어떤 장애물도 집이나 경계선과 겹치지 않는다. 특히 장애물의 y좌표가 집의 y좌표와 같다면, 그 장애물의 x구간은 집의 x구간과 겹치지 않음이 보장된다.

각 집에 대해, 집 전체가 보이는 경계선의 가장 긴 연속 구간의 길이를 소수점 아래 정확히 둘째 자리까지 반올림하여 한 줄에 출력하라. 집 전체가 보이는 경계선 구간이 전혀 없다면 대신 No View를 출력하라.