만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

K볼록껍질

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

요약
서로 다른 N개의 점 중 하나를 제거했을 때 나머지 점의 볼록 껍질 꼭짓점이 정확히 K개가 되는 점의 개수를 구합니다.
난이도

어려움10점 중 8점

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

문제

2차원 평면 위에 서로 다른 NN개의 점이 있다. 이 중 한 점을 지웠을 때, 나머지 N−1N-1개의 점을 포함하는 볼록 껍질의 꼭짓점 개수가 KK가 되어야 한다. 이 조건을 만족하도록 지울 수 있는 점의 수를 구하는 프로그램을 작성하라. 볼록 껍질의 변 위에 점이 여러 개 있으면 양 끝 점만 꼭짓점 개수에 포함한다.

입력

첫째 줄에 점의 개수 NN과 KK가 주어진다. (4≤N≤500 0004 \leq N \leq 500\,000, 3≤K≤N−13 \leq K \leq N-1) 둘째 줄부터 NN개의 줄에 걸쳐 각 점의 xx좌표와 yy좌표가 공백으로 구분되어 주어진다. 각 좌표의 절댓값은 10910^9 이하인 정수이며, 점들의 위치는 서로 다르다.

출력

지울 수 있는 점의 수를 출력한다.

힌트

한 점을 지웠을 때 나머지 점들이 일직선 위에 있으면 볼록 껍질은 꼭짓점 두 개로 이루어지므로 이 경우는 세지 않는다.

예제5

  1. 예제 1

    입력
    8 7
-2 -1
-2 1
-1 -2
-1 2
1 -2
1 2
2 -1
2 1
    예상 출력
    8

  2. 예제 2

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

  3. 예제 3

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

  4. 예제 4

    입력
    9 4
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
    예상 출력
    5

  5. 예제 5

    입력
    9 5
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
    예상 출력
    4