Chúng ta được cung cấp số N và tọa độ của hai điểm (x1, y1) và (x2, y2) cho mỗi dòng. Mục tiêu là tìm số dòng tối đa từ các dòng cho trước có thể đi qua một điểm sao cho không có hai dòng nào che nhau và không có phép quay nào được thực hiện.
Chúng ta sẽ biểu diễn các đường dưới dạng cặp (m, c) trong đó y =mx + c và m là độ dốc m =y2-y1 / x2-x1
Các đường thẳng có cùng m thì song song cho trước c1! =C2. Chúng tôi sẽ tính các độ dốc riêng biệt (m). Đối với các đường thẳng đứng nếu x1 =x2, độ dốc =INT_MAX khác m.
Hãy để chúng tôi hiểu bằng một ví dụ.
Đầu vào
Line 1 (x1,y1)=(4,10) (x2,y2)=(2,2) Line 2 (x1,y1)=(2,2) (x2,y2)=(1,1)
Đầu ra
Maximum lines: 2
Giải thích - Tổng số dòng là 2. Cả hai đều có độ dốc khác nhau.
Đầu vào
Line 1 (x1,y1)=(1,5) (x2,y2)=(3,2) Line 2 (x1,y1)=(2,7) (x2,y2)=(2,8)
Đầu ra
Maximum lines: 2
Giải thích - Tổng số dòng là 2. Cả hai đều có độ dốc khác nhau.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Mảng số nguyên x1 [] và x2 [] được sử dụng để lưu trữ tọa độ của các điểm trên các dòng.
-
Hàm numLines (int x1 [], int y1 [], int x2 [], int y2 []) đang đếm số dòng đi qua một điểm.
-
Áp dụng công thức cho từng điểm trong x1 [], y1 [], x2 [], y2 [] để tính độ dốc và tăng số lượng độ dốc bằng cách sử dụng k.
-
Mảng s [] lưu trữ giá trị của độ dốc.
-
Trả về k dưới dạng số dò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("Maximum lines: %d", numLines(n, x1, y1, x2, y2));
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Maximum distinct lines passing through a single point : 2