C言語で1つの点を通過する最大の異なる直線数を求める方法

問題の概要

各直線について、2点の座標 (x1, y1) と (x2, y2) が与えられます。この問題の目的は、与えられた直線の中から、1つの点を通過できる直線の最大数を求めることです。ただし、どの2本の直線も互いに重なり合わず、回転も行われないものとします。

直線の表現方法

直線は (m, c) のペアで表現します。ここで y = mx + c であり、m は傾きを表します。傾きは次の式で計算できます。

m = (y2 − y1) / (x2 − x1)

同じ傾き m を持つ直線は、切片が c1 ≠ c2 であれば互いに平行になります。このアルゴリズムでは、異なる傾き(m)の数を数えます。垂直な直線の場合(x1 = x2 のとき)、傾きは INT_MAX とします(サンプルコードでは 999 を使用)。

入力例と出力例

例1

入力

直線1 (x1,y1)=(4,10) (x2,y2)=(2,2)
直線2 (x1,y1)=(2,2) (x2,y2)=(1,1)

出力

最大直線数: 2

説明 − 直線は合計2本あり、両方とも傾きが異なります。

例2

入力

直線1 (x1,y1)=(1,5) (x2,y2)=(3,2)
直線2 (x1,y1)=(2,7) (x2,y2)=(2,8)

出力

最大直線数: 2

説明 − 直線は合計2本あり、両方とも傾きが異なります。

アルゴリズムのアプローチ

• 整数配列 x1[]、y1[]、x2[]、y2[] を使用して、直線上の点の座標を保存します。
• 関数 numLines(int x1[], int y1[], int x2[], int y2[]) が、1つの点を通過する直線の数を数えます。
• 各直線の点に対して傾きを計算する公式を適用し、変数 k を使って傾きのカウントを増やしていきます。
• 配列 s[] は計算された傾きの値を保存します。
• 最後に、直線の数である k を結果として返します。

C言語での実装例

#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;
}

実行結果

上記のコードを実行すると、次の出力が生成されます −

1つの点を通過する最大の異なる直線数: 2