আমাদের N সংখ্যা এবং প্রতিটি রেখার জন্য দুটি বিন্দুর কোঅর্ডিনেট (x1,y1) ও (x2,y2) দেওয়া আছে। লক্ষ্য হলো দেওয়া রেখায় থেকে সর্বোচ্চ কতগুলো রেখা একটি বিন্দুতে থেকে যেতে পারে যাতে কোনো দুটি রেখা একে অপরকে কভার না করে, এবং কোনো রোটেশন করা হয় না।
আমরা রেখাগুলোকে (m,c) জোড়া হিসেবে রিপ্রেজেন্ট করব যেখানে y=mx+c এবং m হলো স্লপ m=y2-y1/x2-x1
সমান m वाले রেখাগুলো প্যারালেল যদি c1!=c2। আমরা স্বতন্ত্র স্লপ (m) কাউন্ট করব। ভের্টিকাল রেখার জন্য যদি x1=x2 হয়, তবে slope = 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
ব্যাখ্যা − মোট রেখা ২। উভয়ের স্লপ আলাদা।
ইনপুট
Line 1 (x1,y1)=(1,5) (x2,y2)=(3,2) Line 2 (x1,y1)=(2,7) (x2,y2)=(2,8)
আউটপুট
Maximum lines: 2
ব্যাখ্যা − মোট রেখা ২। উভয়ের স্লপ আলাদা।
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি
ইন্টিজার অ্যারে x1[] এবং x2[] রেখার পয়েন্টের কোঅর্ডিনেট সংরক্ষণ করতে ব্যবহৃত হয়।
ফাংশন numLines(int x1[],int y1[], int x2[], int y2[]) একক বিন্দুতে থেকে যাওয়া রেখার সংখ্যা গণনা করে।
x1[],y1[],x2[],y2[]-এর প্রতিটি পয়েন্টে স্লপের সূত্র প্রয়োগ করে এবং k ব্যবহার করে স্লপ কাউন্ট ইনক্রিমেন্ট করে।
অ্যারে 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
