ধরুন আমরা y =mx + c আকারে লাইনের সেট করেছি। এই লাইন এবং উল্লম্ব বিভাগ দ্বারা তৈরি বিভাগ আছে. আমাদের প্রদত্ত বিভাগে উপস্থিত ছেদ বিন্দু খুঁজে বের করতে হবে বা নেই। ধরুন লাইনগুলো −
এর মতL1 =y =x + 2
L2 =y =-x + 7
L3 =y =-3
L4 =y =2x - 7
এবং উল্লম্ব অংশটি x =2 থেকে x =4 পর্যন্ত দেওয়া হয়েছে।
এখানে L1 এবং L2 এর ছেদ বিন্দু এই বিভাগের ভিতরে উপস্থিত রয়েছে, তাই উত্তরটি সত্য হবে৷
এই সমস্যা সমাধানের জন্য, আমরা বাছাই কৌশল মামলা করব। প্রথমে, আমরা উল্লম্ব বিভাগের উভয় সীমানা সহ প্রতিটি লাইনের ছেদ বিন্দু গণনা করব। যে পরে একটি জোড়া হিসাবে যে সংরক্ষণ করুন. আমাদের কেবল ছেদগুলির y-স্থানাঙ্কের মানগুলিকে একটি জোড়া হিসাবে সংরক্ষণ করতে হবে কারণ x-স্থানাঙ্কগুলি নিজেই সীমানার সমান৷
এখন আমরা বাম সীমানার সাথে তাদের ছেদগুলির উপর ভিত্তি করে এই জোড়াগুলি সাজাব। এর পরে, আমরা এই জোড়াগুলি একে একে লুপ করব। যদি কোন দুটি পরপর জোড়ার জন্য, বর্তমান জোড়ার দ্বিতীয় মান পূর্ববর্তী জোড়ার দ্বিতীয় মানের থেকে কম হয় তাহলে প্রদত্ত উল্লম্ব বিভাগে অবশ্যই একটি ছেদ থাকতে হবে৷
উদাহরণ
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
class line {
public:
int slope, intercept;
line(){
}
line(int slope, int intercept) : slope(slope), intercept(intercept) {
}
};
int getYCoordinate(line l, int x) {
return (l.slope * x + l.intercept);
}
bool hasIntersectionPoint(line lines[], int left_range, int right_range, int N) {
pair<int, int> y_border[N];
for (int i = 0; i < N; i++)
y_border[i] = make_pair(getYCoordinate(lines[i], left_range), getYCoordinate(lines[i], right_range));
sort(y_border, y_border + N);
for (int i = 1; i < N; i++) {
if (y_border[i].second < y_border[i - 1].second)
return true;
}
return false;
}
int main() {
int N = 4;
int slope[] = { 1, -1, 0, 2 };
int intercept[] = { 2, 7, -3, -7 };
line lines[N];
for (int i = 0; i < N; i++)
lines[i] = line(slope[i], intercept[i]);
int left_range = 2;
int right_range = 4;
if (hasIntersectionPoint(lines, left_range, right_range, N)) {
cout << "The intersection point is lies between " << left_range << " and " << right_range;
} else {
cout << "No intersection point is present in between " << left_range << " and " << right_range;
}
} আউটপুট
The intersection point is lies between 2 and 4
