시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 64 MB (%)
문제
대령 함저엉은 함정에 빠졌다! 며칠간 그는 고원에서 대장 위치로 싸우고 있었고 그의 이동 명령 유닛은 현재 (0,0), 절벽의 가장자리 위치에 멈춰져 버렸다. 하지만 바람은 변한다! 대령은 그의 소매에서 비밀무기를 꺼냈다: 이름하여 "입실론 그물" 당신의 직업은, 대령의 수석 최적화 사무원으로, 그물을 이용해 얻을 수 있는 최대 이득을 결정하는 것이다. 입실론 그물은 낙하산처럼 생긴 기계인데, 볼록한 형태를 감싸도록 개시할 수 있다. (형태가 볼록하다는 것은, 만약 두 점 p,q가 포함되어 있다면, 선분 pq도 모두 포함되는 것이다.) 그물의 형태는 시작점인 (0,0)을 꼭 포함해야 한다. 대장의 P개의 적 유닛 들이 고정된 위치에 있고 대령은 T개의 아군 유닛을 가지고 있다. 이득이란 그물의 형태가 포함하는 적군의 수, 빼기 포함하는 아군의 수이다. 대장은 유닛이 아니다. 당신은 다음을 가정해도 좋다 * 세 점이 한 선위에 있지는 않고, ( 함저엉의 위치(0,0), 적 유닛, 그리고 아군유닛들) * 모든 두 점은 다른 x좌표와 y좌표를 갖으며, * 모든 유닛의 (x,y) 위치는 y>0이며, * 모든 좌표는 정수로 표현되며 절대값이 최대 1 000 000 000이며, 그리고 * 총 수인 P+T는 1에서 100 사이이다.
입력
첫 줄에 P와 T가, 공백을 사이에 두고 주어진다. 그 후 P개의 줄에 적군의 좌표가 x y형태로 주어지며, 다음 T개의 줄에 아군의 좌표가 주어진다.
출력
가능한 최대 이득을 출력한다.
힌트
입력예제 ``` 5 3 -8 4 -7 11 4 10 10 5 8 2 -5 7 -4 3 5 6 ``` 출력예제 ``` 3 ``` 그림1. 예제 입력과 최적 그물배치 ![그림1](/download_file/4691e23d68fb47001995da64d58026dbbf46c8322a4be466301d6165b736c6c3/6.png/?show=true)