부렉 나누기

시간 제한1초메모리 제한128 MB

요약
y축을 기준으로 좌우에 놓인 두 개의 convex polygon 각각의 면적을 동시에 이등분하는 직선 y=Ax+B를 구하는 문제입니다.
난이도

어려움10점 중 8점

유형
이분 탐색, 기하
정답자
아직 제출이 없습니다

문제

미르코와 슬라브코는 아침으로 부렉을 먹으려 한다. 한 조각은 치즈, 다른 한 조각은 고기 속이다. 두 사람은 어느 부렉을 누가 먹을지 정하지 못해 두 부렉을 각각 정확히 절반으로 나누기로 했다. 미르코는 칼을 한 번 곧게 그어 두 부렉을 동시에 같은 넓이의 두 부분으로 자를 수 있다고 말했다. 부렉이 식기 전에 그 선을 찾아야 한다.

그림은 가능한 배치 하나를 보여 준다.

각 부렉은 볼록다각형이다. 한 부렉은 y축의 왼쪽에 완전히 놓이고, 다른 부렉은 y축의 오른쪽에 완전히 놓인다.

두 다각형이 주어졌을 때, 두 부렉을 각각 같은 넓이로 나누는 직선의 방정식을 구하라.

입력

첫 줄에 첫 번째 부렉의 꼭짓점 수 N (3 ≤ N ≤ 5000)이 주어진다.

다음 N줄에는 첫 번째 부렉의 한 꼭짓점 좌표 X와 Y가 십진수로 주어진다 (-1000 < X < 0, -1000 < Y < 1000).

그 다음에는 두 번째 부렉이 같은 형식으로 주어진다. 먼저 꼭짓점 수가 주어지고, 이어서 각 꼭짓점의 좌표가 주어진다.

두 부렉 모두 꼭짓점은 반시계 방향으로 주어진다. 모든 좌표는 소수점 아래 정확히 세 자리로 주어지며, 한 다각형 안에서 세 꼭짓점이 한 직선 위에 놓이는 경우는 없다.

출력

미르코가 사용할 직선을 y = A ⋅ x + B라고 할 때, A와 B를 출력하라. 출력한 값은 정답과 ±0.001 이내로 일치해야 한다.

해는 항상 존재하며 유일하다.

예제2

  1. 예제 1

    입력
    3
    -6.000 1.000
    -2.000 2.000
    -5.000 6.000
    5
    1.000 -1.000
    3.000 -2.000
    6.000 0.000
    4.000 3.000
    1.000 2.000
    
    예상 출력
    -0.319961 1.556489
    
  2. 예제 2

    입력
    4
    -5.000 -1.000
    -3.000 -1.000
    -3.000 6.000
    -5.000 6.000
    4
    3.222 2.000
    5.000 1.000
    5.000 4.000
    3.222 3.000
    
    예상 출력
    0.000000 2.500000