আমাদের প্রতিটি লাইনের জন্য N নম্বর এবং দুটি বিন্দু (x1,y1) এবং (x2,y2) এর স্থানাঙ্ক দেওয়া হয়েছে। লক্ষ্য হল প্রদত্ত রেখাগুলি থেকে সর্বাধিক সংখ্যক লাইন খুঁজে বের করা যা একটি একক বিন্দুর মধ্য দিয়ে যেতে পারে যাতে কোনও দুটি লাইন একে অপরকে ঢেকে না রাখে এবং কোনও ঘূর্ণন সঞ্চালিত হয় না।
আমরা লাইনগুলিকে (m,c) জোড়া হিসাবে উপস্থাপন করব যেখানে y=mx+c এবং m হল ঢাল m=y2-y1/x2-x1
একই m সহ লাইনগুলি সমান্তরাল দেওয়া হয় c1!=c2। আমরা স্বতন্ত্র ঢাল (মি) গণনা করব। উল্লম্ব রেখার জন্য যদি 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 ব্যবহার করে ঢালের সংখ্যা বৃদ্ধি করা।
-
অ্যারে 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
