คำอธิบายปัญหา
สมมติว่าเรามีชุดของเส้นในรูป y = mx + c มีส่วน (sections) ที่ถูกสร้างโดยเส้นเหล่านี้และส่วนแนวตั้ง (vertical section) เราต้องหาว่าจุดตัด (intersection point) อยู่ในส่วนที่กำหนดหรือไม่ สมมติเส้นเป็นดังนี้:
L1 = y = x + 2
L2 = y = -x + 7
L3 = y = -3
L4 = y = 2x - 7
และส่วนแนวตั้งกำหนดจาก x = 2 ถึง x = 4
ที่นี่ จุดตัดของ L1 และ L2 อยู่ภายในส่วนนี้ ดังนั้นคำตอบจะเป็น true
เพื่อแก้ปัญหานี้ เราจะใช้เทคนิคการเรียงลำดับ (sorting) ก่อนอื่น เราจะคำนวณจุดตัดของแต่ละเส้นกับขอบเขตทั้งสองของส่วนแนวตั้ง หลังจากนั้นเก็บเป็นคู่ (pair) เราแค่ต้องเก็บค่า y-coordinate ของจุดตัดเป็นคู่ เพราะ x-coordinates เท่ากับขอบเขตเอง
ตอนนี้ เราจะเรียงคู่เหล่านี้ตามจุดตัดกับขอบซ้าย หลังจากนั้น เราจะวนลูปผ่านคู่เหล่านี้ทีละคู่ ถ้าสำหรับคู่ที่ติดกันสองคู่ ค่าที่สองของคู่ปัจจุบันน้อยกว่าค่าที่สองของคู่ก่อนหน้า แสดงว่าต้องมีจุดตัดในส่วนแนวตั้งที่กำหนด
ตัวอย่างโค้ด
#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
