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

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

성냥은 아이들의 장난감이 아니다

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

요약
n개의 성냥으로 만든 두 도형 A와 B가 주어질 때, 평행이동 후 A가 B와 일치하도록 옮겨야 하는 성냥 개수의 최솟값을 구한다.
난이도

어려움10점 중 9점

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

문제

바샤는 성냥 퍼즐 풀기를 좋아한다. 대개 이런 식으로 제시된다. 성냥으로 만든 그림 AA가 주어질 때, 최소 개수의 성냥을 옮겨 그림 BB를 만들어라.

예를 들어, 현재 상트페테르부르크 청소년 프로그래밍 팀 챔피언십의 번호에서 성냥 세 개만 옮기면 대각선이 있는 마름모를 얻을 수 있다.

바샤가 푸는 퍼즐에는 항상 답이 있다. 즉, 그림 AA에 쓰인 성냥의 집합은 그림 BB에 쓰인 성냥의 집합과 같다. 또한 한 그림 안에서 길이가 0이 아닌 부분이 겹치는 두 성냥은 없다. 다시 말해 성냥은 교차할 수 있지만 겹쳐 놓을 수는 없다.

바샤는 손으로 퍼즐을 푸는 데 지쳐서, 이제 여러분에게 퍼즐을 대신 풀어 줄 프로그램을 작성해 달라고 부탁한다. 프로그램은 그림 AA와 BB의 설명을 입력받아, AA에서 성냥을 최소 몇 개 옮겨야 결과 그림이 BB를 평행 이동한 것과 같아지는지 찾아야 한다.

입력

첫째 줄에 각 그림의 성냥 개수 nn이 정수로 주어진다 (1≤n≤10001 \le n \le 1000).

다음 nn개 줄에는 그림 AA의 성냥 끝점 좌표가 주어진다. ii번 성냥은 두 끝점의 좌표 x_1ix\_{1i}, y_1iy\_{1i}, x_2ix\_{2i}, y_2iy\_{2i}로 나타낸다. 그다음 nn개 줄에는 같은 형식으로 그림 BB의 설명이 주어진다. 이 성냥들의 길이 집합은 그림 AA의 성냥 길이 집합과 같다.

모든 좌표의 절댓값은 10410^4을 넘지 않는다. 모든 성냥의 길이는 0이 아니므로 x_1i≠x_2ix\_{1i} \ne x\_{2i}이거나 y_1i≠y_2iy\_{1i} \ne y\_{2i}이다.

출력

그림 AA가 평행 이동을 무시하고 그림 BB와 일치하도록 옮겨야 하는 성냥의 최소 개수를 출력한다.

예제1

  1. 예제 1

    입력
    5
    0 0 1 2
    1 0 0 2
    2 0 2 2
    4 0 3 2
    4 0 5 2
    9 -1 10 1
    10 1 9 3
    8 1 10 1
    8 1 9 -1
    8 1 9 3
    
    예상 출력
    3