C/C++볼록 다각형 대각선 교점 의 예제 코드

제목 설명
n 개의 정점 의 돌출 다각형 에 대해 서 는 세 개의 대각선 이 하나 도 교차 하지 않 는 다.도형 에서 대각선 교점 의 개 수 를 요청 합 니 다.
예 를 들 어 6 변형:

여기 서 여러 개의 대각선 이 한 점 에 교차 하 는 상황 이 나타 나 지 않 았 음 을 알 수 있다.
입력 형식
입력 은 한 줄 에 정수 n 만 있 고 변 수 를 대표 합 니 다.
출력 형식
한 줄 의 정 수 를 출력 하 는 것 은 답 을 대표 한다.

데이터 규모 와 약정

여기에 특별한 예 를 하나 드 리 겠 습 니 다.
입력:
98765
출력 은:
3964374251598225115
특히 이런 상황 에서 답 의 값 은 롱 롱 롱 유형의 최대 표시 범위 에 가 까 워 졌 기 때문에 계산 하 는 과정 에서 특히 주의해 야 한다.다음은 코드 를 제시한다.

#include <iostream>

using namespace std;

int main()
{
	long long int n = 0;
	cin >> n;
	long long int answer = 0;
	long long int temp = 1;
	while (temp < (n - 2))
	{
		answer += temp * (n - temp - 2);
		temp++;
	}
	if (n % 4 == 0)
	{
		n /= 4;
	}
	else if (n % 2 == 0)
	{
		n /= 2;
		answer /= 2;
	}
	else
	{
		answer /= 4;
	}
	answer *= n;
	cout << answer << endl;
	return 0;
}

먼저 하나의 대각선 을 선택 하고 다각형 을 두 부분 으로 나 누 며 한 쪽 은 한 점 이 고 다른 한 쪽 은 남 은 점 이 며 양쪽 의 점 이 연결 되 어 형 성 된 대각선 은 선택 한 대각선 과 교차 하여 교점 을 형성한다.
이런 식 으로 추정 하면 현 재 는 한 쪽 이 한 점 이 고,그 다음 에 이 쪽 의 점 은 점점 증가 하여 다른 쪽 도 한 점 만 남 을 때 까지 한다.특히 주의해 야 할 것 은 이런 각 조 의 대각선 은 n 개가 있 는데 이렇게 반복 적 으로 계산 했다.예 를 들 어 점 a 에서 점 b 와 점 b 에서 점 a 를 계산 한 것 은 사실은 같은 것 이다.다시 문제 의 뜻 에 따라 모든 교점 은 두 개의 대각선 으로 형 성 된 것 이 고 우 리 는 점 을 계산 할 때 모든 대각선 으로 한 번 계산 하기 때문에 다시 한 번 계산 했다.즉,이렇게 해서 우리 가 얻 은 answer 는 최종 정 답 의 네 배 이다.
특히 나 는 n 을 곱 한 조작 을 밖으로 옮 기 고 4 를 나 누 는 조작 을 앞 당 겨 연산 과정 에서 데이터 가 넘 치 는 상황 이 발생 하지 않도록 주의해 야 한다.
여기 서 C/C++볼록 다각형 의 대각선 교점 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++볼록 다각형 의 대각선 교점 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!