頁面無法載入？點擊這裡可能會修復。
Placeholder

#10412

케이크 자르기 45s 1024MB

問題

오늘은 당신과 쌍둥이 형제/자매의 생일이다. 축하하기 위해 함께 나눠 먹을 직사각형 케이크를 준비했다. 케이크 위에는 (서로 겹칠 수도 있는) 삼각형 아이싱 패치가 \mathbf{N}개 올려져 있다. 모든 아이싱 패치는 같은 삼각형 틀로 만들어졌으므로 모양과 방향이 모두 같다. 당신과 쌍둥이는 매우 비슷하지만, 아이싱 취향은 크게 다르다. 이 차이는 각 아이싱 패치마다 두 사람이 느끼는 "만족도"가 서로 다르다고 생각함으로써 모델링된다. 구체적으로 i번째 아이싱 패치 전체를 먹었을 때 당신의 만족도는 \mathbf{A_i}이고, 쌍둥이의 만족도는 \mathbf{B_i}이다. 누군가가 한 패치의 일부만 먹었다면, 먹은 면적에 비례하는 만족도를 얻는다. 예를 들어 당신이 i번째 아이싱 패치 면적의 \frac{2}{3}을 먹었다면, 그 패치로부터 얻는 만족도는 \frac{2\mathbf{A_i}}{3}이다. 또한 당신이나 쌍둥이가 좋아하지 않는 맛이 있을 수 있으므로, \mathbf{A_i}와/또는 \mathbf{B_i}는 음수일 수도 있다.

A cake with 4 icing patches.

케이크를 Y축과 평행한 수직선으로 한 번만 잘라, 두 개의 직사각형 조각으로 나눌 것이다. 자른 뒤에는 당신이 왼쪽 조각을 먹고, 쌍둥이가 오른쪽 조각을 먹는다. 당신의 총 만족도는 자르는 선의 왼쪽에 있는 모든 아이싱으로부터 얻는 만족도의 합이다. 마찬가지로 쌍둥이의 총 만족도는 자르는 선의 오른쪽에 있는 모든 아이싱으로부터 얻는 만족도의 합이다.

가능한 한 공정하게 하기 위해, 당신의 총 만족도와 쌍둥이의 총 만족도의 차이의 절댓값이 가능한 한 작아지도록 케이크를 자르고 싶다. 직사각형 케이크 위에 \mathbf{N}개의 삼각형 아이싱 패치가 주어질 때, 한 번의 수직 절단으로 달성할 수 있는 두 사람 총 만족도의 차이의 절댓값의 최소는 얼마인가?


輸入

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다. 각 테스트 케이스는 먼저 양의 정수 세 개 \mathbf{N}, \mathbf{W}, \mathbf{H}가 주어진 한 줄로 시작한다. 이는 각각 케이크 위 아이싱 패치의 개수와 케이크 윗면의 가로 길이, 세로 길이이다. 케이크의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 오른쪽 위 꼭짓점은 (\mathbf{W}, \mathbf{H})에 있다. 그 다음 한 줄에 아이싱 패치를 만드는 틀(mold)이 주어진다. 이 줄에는 네 정수 \mathbf{P}, \mathbf{Q}, \mathbf{R}, \mathbf{S}가 있으며, 아이싱 패치 틀은 꼭짓점이 (0, 0), (\mathbf{P}, \mathbf{Q}), (\mathbf{R}, \mathbf{S})인 삼각형이다. 그 다음 \mathbf{N}줄이 이어진다. 이 중 i번째 줄에는 네 정수 \mathbf{X_i}, \mathbf{Y_i}, \mathbf{A_i}, \mathbf{B_i}가 주어진다. i번째 패치는 꼭짓점이 (\mathbf{X_i}, \mathbf{Y_i}), (\mathbf{X_i} + \mathbf{P}, \mathbf{Y_i} + \mathbf{Q}), (\mathbf{X_i} + \mathbf{R}, \mathbf{Y_i} + \mathbf{S}) 인 삼각형이다. 당신은 이 패치 전체를 먹으면 만족도 \mathbf{A_i}를 얻고, 쌍둥이는 만족도 \mathbf{B_i}를 얻는다.


輸出

각 테스트 케이스마다 Case #x: y/z 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, \frac{y}{z}는 한 번의 수직 절단으로 달성할 수 있는 당신과 쌍둥이의 총 만족도 차이의 절댓값의 최솟값을 기약분수로 나타낸 값이다. (즉, z는 양수이며 가능한 한 최소여야 한다.)


範例 

4
1 5 5
3 -1 2 2
1 2 -10 5
2 100000000 50000000
80000000 0 40000000 40000000
5000001 2500000 500 -501
15000000 5000000 501 -400
2 10 10
0 2 4 2
2 2 -4 5
4 6 -6 5
3 622460462 608203753
486076103 36373156 502082214 284367873
98895371 126167607 823055173 -740793281
26430289 116311281 -398612375 -223683435
46950301 278229490 766767410 -550292032
Case #1: 5/1
Case #2: 288309900002019999899/320000000000000000
Case #3: 37/4
Case #4: 216757935773010988373334129808263414106891/187470029508637421883991794137967
샘플 케이스 #1에서는 아이싱 구역이 하나뿐이다. 최적 절단은 그 구역의 왼쪽이다. 당신은 아이싱을 먹지 않아 즐거움이 0이고, 쌍둥이는 아이싱 구역 전체를 먹어 즐거움 5를 얻는다. 당신과 쌍둥이의 즐거움 차의 절댓값은 |0 - 5| = 5이다. 샘플 케이스 #2에서는 아이싱 구역이 두 개다. 최적 절단 위치는 X = 15099999.99이다. 답의 분자와 분모가 매우 커질 수 있음을 유의하라. 샘플 케이스 #3에서는 아이싱 구역이 두 개다. 최적 절단 위치는 X = 4이다. 당신은 첫 번째 아이싱 구역의 75%를 먹고 즐거움 -3을 얻는다. 쌍둥이는 첫 번째 구역의 25%와 두 번째 구역 전체를 먹어 5 \cdot 0.25 + 5 = 6.25의 즐거움을 얻는다. 즐거움 차의 절댓값은 |-3 - 6.25| = 9.25 = \frac{37}{4}이다. X = 1에서 자르면 당신의 즐거움은 0, 쌍둥이의 즐거움은 10이 된다. 두 값 모두 X = 4에서의 해당 즐거움보다 크지만, 그 차이는 10 \gt 9.25이므로 X = 4에서 자르는 것이 더 낫다. 샘플 케이스 #4에서는 아이싱 구역이 세 개다. 최적 절단 위치는 X \approx 521241077.6027이다.

來源

GCJ 2021wf A

需要登入才能撰寫程式碼。