백준 3049번 다각형의 대각선 c++ 풀이

문제

세 대각선이 한 점에서 만나지 않는 볼록 N각형이 주어졌을 때, 대각선의 교차점의 개수를 세는 프로그램을 작성하시오.

아래 그림은 위의 조건을 만족하는 한 육각형의 교차점 그림이다.

 

모든 내부각이 180도보다 작은 다각형을 볼록 다각형이라고 한다.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 100)

출력

첫째 줄에 교차점의 개수를 출력한다.

예제 입력 1 복사

3

예제 출력 1 복사

0

예제 입력 2 복사

4

예제 출력 2 복사

1

예제 입력 3 복사

6

예제 출력 3 복사

15

 

교차점이 생기는 조건은 4개의 꼭지점에서 나온 선분이 만나게 되면 교차점이 생기게 된다. 따라서 nC4를 구하게 된다면 교차점의 개수를 구할 수 있다. 

 

n * (n-1) * (n-2) * (n-3) / 24 이렇게 nC4를 구할 수 있게 된다.

 

4개로 나올 수 있는 모든 경우의 수 중 4!인 24를 나누어서 중복을 제거함

 

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n;
    cin >> n;
    cout << n * (n-1) * (n-2) * (n-3) / 24;


    return 0;
}