아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

케이크 두 개

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

요약
무작위 순서로 주어진 두 직사각형의 꼭짓점 네 개씩을 보고, 두 직사각형을 동시에 이등분하는 직선 y = px + q를 찾아 p와 q를 정수 또는 기약분수로 출력한다.
난이도

보통10점 중 7점

유형
기하, 수학, 구현, 정렬
정답자
아직 제출이 없습니다

문제

SUAPC 2023 Summer 출제진을 먹일 NMKNMK개의 2차원 케이크들이 연세대학교 공A527에 배달되었다. 문제를 만드느라 당이 떨어진 출제진은 그만 특별한 케이크 두 개만을 남기고 전부 먹어치우고 말았다.

뒤늦게 도착한 Sinchon ICPC 회장과 공간을 제공한 Morgorithm 회장에게 아직 열지 않은 두 개의 케이크 박스를 바침으로서 분노는 피했지만, 이 두 명은 케이크를 보고 새로운 문제 아이디어가 떠오르고 말았다. 두 개의 케이크가 모두 직사각형 모양이었던 것이다. 두 사람은 머릿속에서 단 한 번의 칼질만으로 두 개의 케이크를 각각 넓이가 같은 두 조각으로 나눌 수 있다는 것은 증명했지만, 당이 떨어진 나머지 실제로 이 칼질이 어떻게 이루어져야 하는지는 출제진에게 맡기고 말았다.

두 사람이 케이크를 전부 먹기 전에, 두 개의 케이크를 각각 넓이가 같은 두 조각으로 나눌 수 있도록 하는 칼질이 어떻게 이루어져야 하는지 구해 보자.

입력

첫 번째 줄부터 44개의 줄에 걸쳐, 첫 번째 케이크 꼭지점의 xx좌표와 yy좌표를 나타내는 정수 x_1,i,y_1,ix\_{1,i}, y\_{1,i}이 공백으로 구분되어 주어진다. (1≤i≤4;(1 \leq i \leq 4; −100,000≤x_1,i,y_1,i≤100,000)-100\\,000 \le x\_{1,i}, y\_{1,i} \le 100\\,000)

다섯 번째 줄부터 44개의 줄에 걸쳐, 두 번째 케이크 꼭지점의 xx좌표와 yy좌표를 나타내는 정수 x_2,i,y_2,ix\_{2,i}, y\_{2,i}이 공백으로 구분되어 주어진다. (1≤i≤4;(1 \leq i \leq 4; −100,000≤x_2,i,y_2,i≤100,000)-100\\,000 \le x\_{2,i}, y\_{2,i} \le 100\\,000)

케이크는 항상 비어 있지 않은 직사각형이며, 케이크 꼭지점의 점 순서는 무작위로 주어짐에 유의하라. 또한, 두 케이크가 어느 한 점에서 만나는 경우나 yy축에 평행하게 칼질하는 법이 존재하는 경우는 주어지지 않는다.

출력

칼질이 직선 y=px+qy=px+q의 일부일 때, 첫째 줄에 p,qp,q를 공백으로 구분하여 출력한다. 답이 여러 개라면 아무거나 출력한다.

단, pp나 qq가 정수일 경우 그대로 출력하고, 정수가 아닐 경우 출력하려는 수가 ab\frac{a}{b} 라면 aa와 bb를 ‘/’로 구분하여 출력한다. (a,b(a,b는 정수, b>0b>0, gcd⁡(a,b)=1)\gcd(a,b)=1)

계산 및 출력 과정에서 3232비트 정수의 범위를 넘을 수 있음에 유의하라.

예제3

  1. 예제 1

    입력
    0 0
    0 1
    1 0
    1 1
    2 1
    3 2
    3 1
    2 2
    
    예상 출력
    1/2 1/4
    
  2. 예제 2

    입력
    -2 -1
    -1 6
    -4 5
    1 0
    10 -8
    -3 -8
    1 -2
    6 -14
    
    예상 출력
    -21/10 -13/20
    
  3. 예제 3

    입력
    0 2
    1 0
    1 2
    0 0
    0 -2
    0 -4
    -3 -4
    -3 -2
    
    예상 출력
    2 0