หาจำนวนเส้นตรงสูงสุดที่ผ่านจุดเดียวกันใน C

โจทย์

กำหนด N เส้นตรง แต่ละเส้นได้จาก 2 จุด (x1,y1), (x2,y2) หา **จำนวนเส้นสูงสุดที่ผ่านจุดเดียวกัน** โดยไม่มีเส้นไหนทับซ้อน (Coincident) และไม่หมุนเส้น

แนวคิดแก้ปัญหา

• แต่ละเส้นแทนด้วย **Slope (m)** และ **Intercept (c)**: y = mx + c
• Slope m = (y2 - y1) / (x2 - x1)
• เส้นที่มี **Slope เท่ากัน** = ขนาน (Parallel)
• เส้นที่มี **Slope และ Intercept เท่ากัน** = ทับซ้อน (Coincident) → นับ 1 เส้น
• โจทย์ถาม: **จำนวน Slope ที่ต่างกันสูงสุด** (Distinct Slopes)

การจัดการ Vertical Line

• ถ้า x1 == x2 → Vertical Line → Slope = Infinity
• แทนด้วยค่าพิเศษ เช่น INT_MAX หรือ INFINITY

ตัวอย่างโปรแกรม

#include 
#include 
#include 

#define MAX_LINES 100

int countDistinctSlopes(int n, int x1[], int y1[], int x2[], int y2[]) {
    double slopes[MAX_LINES];
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        double slope;
        
        if (x1[i] == x2[i]) {
            slope = INFINITY; // Vertical line
        } else {
            slope = (double)(y2[i] - y1[i]) / (x2[i] - x1[i]);
        }
        
        // Check if slope already exists (with epsilon for float comparison)
        int found = 0;
        for (int j = 0; j < count; j++) {
            if (isinf(slopes[j]) && isinf(slope)) {
                found = 1; break;
            }
            if (fabs(slopes[j] - slope) < 1e-9) {
                found = 1; break;
            }
        }
        
        if (!found) {
            slopes[count++] = slope;
        }
    }
    return count;
}

int main() {
    // Example 1
    int x1[] = {4, 2}, y1[] = {10, 2};
    int x2[] = {2, 1}, y2[] = {2, 1};
    int n = 2;
    printf("Max distinct lines: %d\n", countDistinctSlopes(n, x1, y1, x2, y2));
    // Line 1: (4,10)-(2,2) → m = (2-10)/(2-4) = -8/-2 = 4
    // Line 2: (2,2)-(1,1) → m = (1-2)/(1-2) = -1/-1 = 1
    // Distinct slopes: 4, 1 → Count = 2
    
    // Example 2
    int x3[] = {1, 2}, y3[] = {5, 7};
    int x4[] = {3, 2}, y4[] = {2, 8};
    n = 2;
    printf("Max distinct lines: %d\n", countDistinctSlopes(n, x3, y3, x4, y4));
    // Line 1: m = (2-5)/(3-1) = -3/2 = -1.5
    // Line 2: Vertical (x=2) → INF
    // Distinct: 2
    
    return 0;
}

ผลลัพธ์:

Max distinct lines: 2
Max distinct lines: 2

ข้อควรระวังเรื่อง Floating Point

• เปรียบเทียบ Double ด้วย **Epsilon** (fabs(a-b) < 1e-9)
• ใช้ INFINITY (จาก <math.h>) สำหรับ Vertical Lines
• พิจารณาใช้ Rational Numbers (เก็บตัวเศษ/ตัวส่วนแยก) เพื่อ Precision เต็มที่

การขยาย: นับเส้นที่ผ่านจุดเดียวกันจริง (Concurrent Lines)

โจทย์นี้อาจหมายถึง: หาจุดที่มีเส้นผ่านมากที่สุด (Arrangement of Lines)

→ ต้องคำนวณ Intersection ทุกคู่ O(n²) → นับ Frequency ของแต่ละจุด → หา Max

ซับซ้อนกว่า และต้องจัดการ Precision อย่างระมัดระวัง