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

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

크랭크샤프트

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

요약
시계 방향으로 주어진 여러 다각형 판의 면적 가중 무게중심을 구해 각 좌표를 기약분수로 출력한다.
난이도

보통10점 중 6점

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

문제

크랭크샤프트 설계를 위한 CAD 시스템을 개발하고 있다. 각 크랭크샤프트는 NN개의 금속판으로 이루어지며, 0<N≤1000 < N \le 100이다. 모든 판은 같은 합금으로 만들어졌고 두께도 모두 같으므로, 각 판의 밀도와 두께는 균일하다. 각 판은 ViV_i개의 꼭짓점을 가진 다각형이며 3≤Vi≤2003 \le V_i \le 200이다. 모든 판은 서로 평행한 평면에 놓여 있고 단단히 연결되어 있으며, 크랭크샤프트를 구성하는 유일한 요소이다.

이 시스템은 크랭크샤프트의 회전축을 찾아야 한다. 회전축이란 판이 이루는 평면에 수직이면서, 그 축을 중심으로 회전할 때 진동이 가장 작아지는 직선이다. 이러한 축은 반드시 크랭크샤프트 전체의 질량 중심을 지나므로, 문제는 그 질량 중심 (XR,YR)(X_R, Y_R)을 구하는 것으로 귀결된다.

각 판은 판 표면과 평행한 OXYOXY 평면을 갖는 직교좌표계에서의 꼭짓점 좌표로 저장된다. 모든 좌표는 정수이며, 1≤j≤Vi1 \le j \le V_i와 1≤i≤N1 \le i \le N에 대해 −104≤Xij,Yij≤104-10^4 \le X_{ij}, Y_{ij} \le 10^4이다. 각 판의 꼭짓점은 시계 방향으로 나열된다(OXOX축은 오른쪽, OYOY축은 위쪽). 서로 떨어진 둘 이상의 부분으로 이루어진, 아직 완성되지 않은 크랭크샤프트에 대해서도 정답을 출력해야 한다. 이때 모든 부분은 단단히 연결되어 있다고 가정한다.

입력

입력은 공백 또는 줄바꿈으로 구분된 정수들로 이루어지며, 다음 순서로 주어진다.

  • NN — 판의 개수.
  • 이어서 각 판 ii(1≤i≤N1 \le i \le N)마다 꼭짓점 개수 ViV_i가 주어지고, 그 뒤에 ViV_i개의 꼭짓점 좌표쌍 Xi1 Yi1 … XiVi YiViX_{i1}\ Y_{i1}\ \ldots\ X_{iV_i}\ Y_{iV_i}가 주어진다.

출력

모든 좌표가 정수들의 비이므로 질량 중심은 항상 유리수이다. 회전축의 두 좌표 XRX_R과 YRY_R을 각각 기약분수 p/q 형태로 출력한다. 여기서 q>0q > 0이고 gcd⁡(∣p∣,q)=1\gcd(|p|, q) = 1이다. 좌표가 정수이면 p/1로 쓴다(예를 들어 정수 00은 0/1로 쓴다). 두 분수를 한 줄에 공백 하나로 구분하여 출력한다.

예제4

  1. 예제 1

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

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

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

    입력
    1
    4 2 3 2 7 5 7 5 3
    
    예상 출력
    7/2 5/1