스카이라인

프로그램 명: ncpc_skyline(special judge)

제한시간: 1 초

이것은 빌딩들을 임의의 좌표에 할당했을때 우리가 그 빌딩들이 최대 몇%까지 보이는지 구하는 문제입니다.

좌표대로 빌딩을 지었다고 했을때 지은 빌딩들의 그림을 그래프상으로 정면으로 보았을때

가장 첫번째로 입력한 빌딩이 가장 앞에 있고, 두번째는 그 뒤에, 세번째는 두번째 뒤에... 그리고 이 빌딩들이 전체중 몇%나 보이는지 출력하는 프로그램입니다.

입력

가장 첫번째 입력은 빌딩의 개수입니다.
두번째 입력부터 빌딩의 좌표를 서술합니다.

4개의 빌딩을 짓는다고 가정합시다.
빌딩은 사각형으로 주어지는데 첫번째 입력하는 숫자는 빌딩의 왼쪽끝 좌표 두번째 입력하는 숫자는 빌딩의 왼쪽 높이 세번째 입력하는 숫자는 빌딩의 오른쪽끝 좌표 네번째 입력하는 숫자는 빌딩의 오른쪽 높이 입니다.

출력

빌딩이 각각 몇%나 보이는지 출력합니다. 앞에서 말했듯이 정면에서 보았을때 입니다. 숫자는 소수점 8자리까지 출력합니다.

절대 오차가 10^-6 보다 작으면 정답으로 간주합니다.

입출력 예

입력 

4 
2 3 7 5 
4 6 9 2 
11 4 15 4 
13 2 20 2 

출력 

1.00000000 
0.38083333 
1.00000000 
0.71428571 

입력 

5 
200 1200 400 700 
1200 1400 1700 900 
5000 300 7000 900 
8200 400 8900 1300 
0 1000 10000 800 

출력 

1.00000000 
1.00000000 
1.00000000 
1.00000000 
0.73667852

Last time I visited Shanghai I admired its beautiful skyline. It also got me thinking, "Hmm, how much of the buildings do I actually see?" since the buildings wholly or partially cover each other when viewed from a distance.

In this problem, we assume that all buildings have a trapezoid shape when viewed from a distance. That is, vertical walls but a roof that may slope. Given the coordinates of the buildings, calculate how large part of each building that is visible to you (i.e. not covered by other buildings).

입력

The first line contains an integer, N (2 <= N <= 100), the number of buildings in the city.
Then follows N lines each describing a building. Each such line contains 4 integers, x1, y1, x2, and y2 (0 <= x1 < x2 <= 10000; 0 < y1, y2 <= 10000). The buildings are given in distance order, the first building being the one closest to you, and so on.

출력

For each building, output a line containing a floating point number between 0 and 1, the relative visible part of the building. The absolute error for each building must be < 10^-6.

입출력 예

입력

4
2 3 7 5
4 6 9 2
11 4 15 4
13 2 20 2

출력

1.00000000
0.38083333
1.00000000
0.71428571

입력

5
200 1200 400 700
1200 1400 1700 900
5000 300 7000 900
8200 400 8900 1300
0 1000 10000 800

출력

1.00000000
1.00000000
1.00000000
1.00000000
0.73667852

출처:ncpc/2010/Problem J
번역:ironamor

[질/답] [제출 현황] [푼 후(0)]

[ 채 점 ] [홈으로] [뒤 로]