Số đường thẳng tối đa đi qua một điểm trong C

Cho số N và tọa độ hai điểm (x1,y1), (x2,y2) cho mỗi đường thẳng. Mục tiêu tìm số đường thẳng tối đa từ các đường cho trước có thể đi qua một điểm sao cho không hai đường thẳng nào trùng nhau, và không xoay.

Đại diện đường thẳng bằng cặp (m, c) với y = mx + c, m là độ dốc m = (y2-y1)/(x2-x1).

Các đường thẳng cùng m là song song (c1 != c2). Đếm số độ dốc (m) khác nhau. Đối với đường thẳng đứng x1=x2, độ dốc = INT_MAX.

Hiểu qua ví dụ.

Đầu vào

Đường 1 (x1,y1)=(4,10) (x2,y2)=(2,2)
Đường 2 (x1,y1)=(2,2) (x2,y2)=(1,1)

Đầu ra

Số đường tối đa: 2

Giải thích - Tổng 2 đường, độ dốc khác nhau.

Đầu vào

Đường 1 (x1,y1)=(1,5) (x2,y2)=(3,2)
Đường 2 (x1,y1)=(2,7) (x2,y2)=(2,8)

Đầu ra

Số đường tối đa: 2

Giải thích - Tổng 2 đường, độ dốc khác nhau.

Phương pháp dùng trong chương trình

• Mảng nguyên x1[], x2[] lưu tọa độ điểm trên đường.

• Hàm numLines(int x1[], int y1[], int x2[], int y2[]) đếm số đường qua một điểm.

• Áp dụng công thức cho mỗi điểm tính độ dốc và tăng đếm dùng k.

• Mảng s[] lưu giá trị độ dốc.

• Trả về k là số đường trong kết quả.

Ví dụ

#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("So duong toi da: %d", numLines(n, x1, y1, x2, y2));
    return 0;
}

Kết quả

Chạy code trên cho đầu ra:

So duong thang phan biet qua mot diem: 2