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

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

카렐리야식 점술

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

요약
일반 위치에 있는 N개 점에서 꼭짓점을 골라 만들 수 있는 볼록 K각형의 개수를 여러 K 값에 대해 구한다.
난이도

보통10점 중 7점

유형
조합론, 기하, 동적 계획법, 정렬
정답자
아직 제출이 없습니다

문제

Юкка는 별로 점을 치는 것을 아주 좋아하지만 하늘이 흐린 날이 많아서 별이 그려진 지도를 사용해 점을 친다. 지도에는 NN개의 별이 그려져 있다. 점을 치려면 별 중에서 KK개를 골라야 하고, 이 점들을 꼭짓점으로 하는 다각형이 볼록다각형이면 점이 성공한 것으로 본다. 다각형의 각 변을 지나는 직선에 대해 모든 꼭짓점이 그 직선의 같은 쪽에 있거나 직선 위에 있으면 그 다각형은 볼록하다.

Пекка는 Юкка가 점을 치는 모습을 보다가, 주어진 점들 중에서 꼭짓점을 골라 만들 수 있는 서로 다른 볼록 KK각형의 개수가 몇 개인지 궁금해졌다.

여러 가지 KK 값에 대해 이 질문의 답을 구하시오.

입력

첫째 줄에 점의 개수 NN과 살펴볼 경우의 수 LL이 주어진다 (3≤N≤303 \le N \le 30, 1≤L≤N−21 \le L \le N-2). 다음 NN개 줄에 점의 좌표 XiX_i, YiY_i가 정수로 주어진다 (−10 000≤Xi,Yi≤10 000-10\,000 \le X_i, Y_i \le 10\,000). 어떤 세 점도 한 직선 위에 있지 않고 서로 겹치지 않는다.

마지막 줄에 주어지는 LL개의 서로 다른 KK 값에 대해 볼록다각형의 개수를 구해야 한다. LL개의 수는 모두 양의 정수이고 각각 3 이상 NN 이하이다.

출력

첫째 줄에 각 경우의 답 LL개를 공백으로 구분해 출력한다.

예제1

  1. 예제 1

    입력
    5 3
    0 0
    4 4
    0 4
    4 0
    2 3
    3 4 5
    
    예상 출력
    10 3 0