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

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

소 컬링

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

요약
상대 팀 돌 세 개가 이루는 삼각형 안에 들어가는 돌 개수를 양 팀에 대해 구합니다.
난이도

보통10점 중 7점

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

문제

소들의 겨울 축제인 무림픽(Moolympics)에서 소 컬링은 인기 종목이다.

보통 컬링처럼 두 팀이 겨루고, 각 팀은 무거운 스톤 NN개를 얼음판 위로 밀어 보낸다(3≤N≤500003 \le N \le 50000). 경기가 끝나면 얼음판 위에 스톤 2N2N개가 놓이고, 스톤의 위치는 모두 서로 다른 평면 위의 점이다.

점수를 세는 방식은 조금 특이하다. 어떤 스톤이 상대 팀 스톤 세 개를 꼭짓점으로 하는 삼각형 안에 들어 있으면 그 스톤은 잡힌 것이다. 삼각형의 경계 위에 놓인 스톤도 잡힌 것으로 센다. 한 팀의 점수는 잡힌 상대 팀 스톤의 개수다.

스톤 2N2N개의 위치가 주어질 때, 이 경기의 최종 점수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 NN이 주어진다.

다음 NN개 줄에는 A팀 스톤의 xx좌표와 yy좌표가 정수 두 개로 주어진다.

그다음 NN개 줄에는 B팀 스톤의 xx좌표와 yy좌표가 정수 두 개로 주어진다.

모든 좌표는 −40000-40000 이상 4000040000 이하의 정수이고, 스톤 2N2N개의 위치는 서로 다르다.

출력

첫째 줄에 A팀의 점수와 B팀의 점수를 공백으로 구분해 출력한다.

예제1

  1. 예제 1

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