위험에 빠진 숲

지난 수십 년간 삼림이 크게 훼손되면서 Nlogonia의 강들은 유량이 뚜렷하게 줄었다. Nlogonia는 기술 데이터를 바탕으로 결정을 내리는 선진국이므로, 국가 지도자는 미래 세대에게 물을 보장하기 위해 어떤 조처를 취해야 하는지 파악하려고 일련의 연구를 의뢰했다.

연구에 참여한 과학자들이 작성한 기술 보고서의 결론은 명확했다. 국가 영토의 일정 비율은 식생을 보존해야 한다. 게다가 강 근처 지역은 가장 잘 보존되어야 한다.

새 환경 법규가 시행되며, 강둑에서 일정 거리까지의 지역이 보존 구역이 된다. 이 거리의 이상적인 값은 아직 정해지지 않았지만, 기술 보고서는 보존해야 할 국가 영토의 비율을 이미 정했다.

당신의 기술력을 고려하여, 요구되는 보존 면적 비율을 달성하기 위해 강 주변에서 어느 정도 거리를 보존해야 하는지 밝혀 달라는 의뢰를 받았다.

Nlogonia의 강은 평면에서 축에 평행한 선분으로 나타낼 수 있다. 거리 r이 주어졌을 때, 보존할 영토의 면적은 다음과 같이 정해진다. 각 강마다, 주변 보존 구역은 강을 나타내는 선분을 포함하는 가장 작은 직사각형에 해당하며, 선분 위의 임의의 점과 직사각형 밖의 임의의 점 사이에 최소 r 단위의 거리가 있도록 한다. Nlogonia의 영토는 축에 평행한 변을 가진 직사각형으로 정의되며, 모든 강은 영토의 어떤 변과 평행하다.

1과 100 사이의 정수 P가 주어졌을 때, Nlogonia 영토의 P % 보존을 보장하는 가장 작은 정수 r의 값을 구해야 한다.

아래 그림은 입력의 첫 번째 예제를 보여 준다. Nlogonia의 영토는 점선 영역으로, 보존 구역은 회색 영역으로 나타나 있다.

첫 번째 줄에는 Nlogonia의 강을 나타내는 선분의 개수 N (1 ≤ N ≤ 104)이 주어진다. 다음 N개 줄에는 각각 4개의 정수 x1, y1, x2, y2가 주어지며, (x1, y1)과 (x2, y2)는 강을 나타내는 직선의 양 끝점이다. Nlogonia의 강은 국경과 평행하므로 x1 = x2 또는 y1 = y2임이 보장된다.

그다음 줄에는 보존해야 하는 영토의 최소 비율을 나타내는 정수 P (1 ≤ P ≤ 100)가 주어진다. 마지막 줄에는 4개의 정수 x1, y1, x2, y2가 주어지며, (x1, y1)은 Nlogonia의 영토를 나타내는 직사각형의 왼쪽 아래 모서리이고 (x2, y2)는 오른쪽 위 모서리이다. 이 직사각형의 변은 좌표축에 평행하다.

입력에 주어지는 모든 좌표는 0과 105 사이의 정수이다. 모든 강은 Nlogonia 영토 안에 완전히 포함되어 있다고 가정할 수 있다.

프로그램은 Nlogonia 영토의 P % 보존을 보장하기 위해 r로 설정할 수 있는 최소 정수 r을 한 줄에 출력해야 한다.