두 개의 평행선으로 모든 좌표 점을 표현할 수 있는지 확인하는 C++ 프로그램

이 글에서는 주어진 모든 좌표 점을 단 두 개의 평행선만으로 표현할 수 있는지 확인하는 C++ 프로그램을 살펴보겠습니다.

문제 이해하기

정수 배열이 하나 주어지며, 각 좌표는 (i, arr[i]) 형태로 정의됩니다. 예를 들어 다음과 같은 배열이 있다고 가정해 보겠습니다.

arr = {2,6,8,12,14}

이 경우 점들은 두 개의 평행선에 배치할 수 있습니다. 첫 번째 선에는 (1,2), (3,8), (5,14)가 속하고, 두 번째 선에는 나머지 좌표인 (2,6), (4,12)가 속합니다.

접근 방법

이 문제는 직선의 기울기(slope)를 비교하는 방식으로 해결할 수 있습니다. 두 점 (a1, b1)과 (a2, b2)를 지나는 직선의 기울기는 다음과 같이 계산됩니다.

slope = (b2 - b1) / (a2 - a1)

배열에서 임의의 세 점을 선택했을 때, 직선이 두 개뿐이라면 세 점 중 반드시 두 점은 같은 직선 위에 존재해야 합니다. 따라서 처음 세 점에서 도출할 수 있는 기울기 후보들을 구한 뒤, 각 후보 기울기에 대해 모든 점의 절편(intercept) 값을 계산합니다.

계산된 절편 값이 정확히 두 종류라면 배열의 모든 점을 두 개의 평행선으로 표현할 수 있는 것이고, 그렇지 않다면 불가능합니다.

프로그램은 조건이 성립하면 1, 그렇지 않으면 0을 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
// 절편 값이 정확히 두 개인지 확인하는 함수
bool is_intercept(double slope, int arr[], int num) {
   set<double> Lines;
   for (int i = 0; i < num; i++)
      Lines.insert(arr[i] - slope * (i));
   return Lines.size() == 2;
}
// 주어진 점들의 기울기를 확인하는 함수
bool is_parallel(int arr[], int num) {
   bool slope1 = is_intercept(arr[1] - arr[0], arr, num);
   bool slope2 = is_intercept(arr[2] - arr[1], arr, num);
   bool slope3 = is_intercept((arr[2] - arr[0]) / 2, arr, num);
   return (slope1 || slope2 || slope3);
}
int main() {
   int arr[] = {2,6,8,12,14};
   int num = sizeof(arr)/sizeof(arr[0]);
   cout << (int)is_parallel(arr, num);
   return 0;
}

코드 설명

is_intercept() 함수는 주어진 기울기에 대해 각 점의 절편(arr[i] − slope × i)을 집합(set)에 저장하고, 서로 다른 절편의 개수가 정확히 2개인지 판별합니다. is_parallel() 함수는 처음 세 점에서 만들 수 있는 세 가지 기울기 후보를 차례로 검사하여, 그중 하나라도 조건을 만족하면 true를 반환합니다.

출력

1