เส้นที่ชัดเจนสูงสุดที่ผ่านจุดเดียวใน C

เราได้รับหมายเลข N และพิกัดของสองจุด (x1,y1) และ (x2,y2) สำหรับแต่ละบรรทัด เป้าหมายคือการหาจำนวนเส้นสูงสุดจากเส้นที่กำหนดที่สามารถผ่านจุดเดียวได้ โดยไม่ให้เส้นสองเส้นมาทับกัน และไม่มีการหมุนใดๆ

เราจะแสดงเส้นเป็นคู่ของ (m,c) โดยที่ y=mx+c และ m คือความชัน m=y2-y1/x2-x1

เส้นที่มี m เท่ากันจะขนานกันเมื่อ c1!=c2 เราจะนับความชันที่แตกต่างกัน(m) สำหรับเส้นแนวตั้งถ้า 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[] และ x2[] ใช้เพื่อจัดเก็บพิกัดของจุดบนเส้น

• ฟังก์ชัน numLines(int x1[],int y1[], int x2[], int y2[]) กำลังนับจำนวนบรรทัดที่ผ่านจุดเดียว

• ใช้สูตรสำหรับแต่ละจุดใน x1[],y1[],x2[],y2[] เพื่อคำนวณความชันและเพิ่มจำนวนความชันโดยใช้ k

• Array 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