이 문제에서는 직선의 개수 N과 각 직선을 정의하는 두 점의 좌표 (x1, y1), (x2, y2)가 주어집니다. 목표는 주어진 직선들 중 두 직선이 서로 겹쳐 덮지 않으면서 하나의 점을 통과할 수 있는 직선의 최대 개수를 구하는 것이며, 회전은 고려하지 않습니다.
직선은 일반적으로 (m, c) 쌍으로 표현합니다. 여기서 y = mx + c 형태이며, m은 기울기입니다. 기울기는 다음 공식으로 계산됩니다.
m = (y2 - y1) / (x2 - x1)
기울기(m)가 같지만 c1 ≠ c2인 두 직선은 서로 평행합니다. 따라서 서로 다른 기울기의 개수만 세면 됩니다. 수직선의 경우 x1 = x2이므로 기울기를 INT_MAX로 처리하고, 그 외에는 계산된 m 값을 그대로 사용합니다.
예제로 이해하기
입력
Line 1 (x1,y1)=(4,10) (x2,y2)=(2,2) Line 2 (x1,y1)=(2,2) (x2,y2)=(1,1)
출력
Maximum lines: 2
설명 − 전체 직선은 2개이며, 두 직선의 기울기가 서로 다르므로 모두 유효하게 계산됩니다.
입력
Line 1 (x1,y1)=(1,5) (x2,y2)=(3,2) Line 2 (x1,y1)=(2,7) (x2,y2)=(2,8)
출력
Maximum lines: 2
설명 − 전체 직선은 2개이며, 두 직선의 기울기가 서로 다릅니다.
프로그램에 사용된 접근 방식
- 정수 배열 x1[], y1[], x2[], y2[]는 각 직선 위의 점 좌표를 저장합니다.
- numLines(int n, int x1[], int y1[], int x2[], int y2[]) 함수는 한 점을 통과하는 직선의 개수를 계산합니다.
- 각 직선의 좌표에 기울기 공식을 적용하여 기울기를 구하고, 변수 k를 통해 개수를 증가시킵니다.
- 배열 s[]는 계산된 기울기 값을 저장합니다.
- k를 결과값으로 반환하여 직선의 개수를 출력합니다.
예제 코드
#include <stdio.h>
int numLines(int n, int x1[], int y1[], int x2[], int y2[]){
double s[10];
int k=0;
double slope;
for (int i = 0; i < n; ++i) {
if (x1[i] == x2[i])
slope = 999;
else
slope = (y2[i] - y1[i]) * 1.0 / (x2[i] - x1[i]) * 1.0;
s[k++]=slope;
}
return k;
}
int main(){
int n = 2;
int x1[] = { 1, 5 }, y1[] = { 3, 2 };
int x2[] = { 2,7 }, y2[] = { 2, 8 };
printf("Maximum lines: %d", numLines(n, x1, y1, x2, y2));
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Maximum distinct lines passing through a single point : 2