y = mx + c রূপে কিছু রেখা দেওয়া আছে। একটি লম্বা সেকশন (x = left থেকে x = right) দেওয়া আছে। এই সেকশনের ভিতরে কোনো দুটি রেখা কাটা কিনা তা যাচাই করতে হবে।
উদাহরণ: L1: y = x + 2, L2: y = -x + 7, L3: y = -3, L4: y = 2x - 7। সেকশন x = 2 থেকে x = 4। এখানে L1 এবং L2-এর কাটানোর বিন্দু সেকশনের ভিতরে পড়ে, তাই উত্তর true।
- প্রতিটি রেখার বাম ও ডান সীমান্তের সাথে কাটানোর বিন্দুর y-কোর্ডিনেট বের করে জোড়া হিসেবে রাখুন।
- বাম সীমান্তের y-মান অনুযায়ী জোড়াগুলো সর্ট করুন।
- क्रमাগত দুটি জোড়া যাচাই করুন: যদি বর্তমান জোড়ার ডান y-মান পূর্ববর্তী জোড়ার ডান y-মান থেকে ছোট হয়, তবে সেকশনের ভিতরে কাটানোর বিন্দু আছে।
#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, 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
