इस लेख में, हम दिए गए क्षैतिज और ऊर्ध्वाधर रेखा खंडों के प्रतिच्छेदन बिंदुओं को मिलाकर बनने वाले त्रिभुजों की संख्या ज्ञात करने के लिए एक कार्यक्रम पर चर्चा करेंगे।
उदाहरण के लिए, मान लीजिए कि हमें निम्नलिखित रेखाखंड दिए गए हैं। इसमें हमारे पास 3 चौराहे बिंदु हैं। तो इन बिंदुओं का उपयोग करके जितने त्रिभुज बनाए जा सकते हैं, वे 3 . होंगे सी<उप>2 ।
| ---|--------|-- | | | --|---| | |
हम स्वीप लाइन एल्गोरिथम का पालन करेंगे। हम रेखाखंडों के सभी मानों को संग्रहीत करेंगे और फिर जाँच करेंगे कि क्या किसी एक रेखा के अंदर के बिंदुओं की तुलना किसी अन्य रेखा के आंतरिक बिंदुओं से भी की जाती है। इस तरह हम दिए गए रेखाखंडों के लिए सभी प्रतिच्छेदन बिंदु प्राप्त कर सकते हैं और फिर हम विभिन्न संभावित संयोजनों का उपयोग करके आसानी से संभावित त्रिभुजों की संख्या ज्ञात कर सकते हैं।
उदाहरण
#include<bits/stdc++.h>
#define maxy 1000005
#define maxn 10005
using namespace std;
//to store intersection points
struct i_point {
int x, y;
i_point(int a, int b) {
x = a, y = b;
}
};
int bit[maxy];
vector < pair <i_point, int> > events;
//to sort the given points
bool com_points(pair<i_point, int> &a, pair<i_point, int> &b) {
if ( a.first.x != b.first.x )
return a.first.x < b.first.x;
else {
if (a.second == 3 && b.second == 3) {
return true;
}
else if (a.second == 1 && b.second == 3) {
return true;
}
else if (a.second == 3 && b.second == 1) {
return false;
}
else if (a.second == 2 && b.second == 3) {
return false;
}
return true;
}
}
void topdate_line(int index, int value) {
while (index < maxn) {
bit[index] += value;
index += index & (-index);
}
}
int query(int index) {
int res = 0;
while (index > 0) {
res += bit[index];
index -= index & (-index);
}
return res;
}
//to insert a line segment
void insertLine(i_point a, i_point b) {
//in case of horizontal line
if (a.y == b.y) {
int begin = min(a.x, b.x);
int end = max(a.x, b.x);
events.push_back(make_pair(i_point(begin, a.y), 1));
events.push_back(make_pair(i_point(end, a.y), 2));
}
//in case of vertical line
else {
int top = max(b.y, a.y);
int bottom = min(b.y, a.y);
events.push_back(make_pair(i_point(a.x, top), 3));
events.push_back(make_pair(i_point(a.x, bottom), 3));
}
}
//to calculate number of intersection points
int calc_i_points() {
int i_points = 0;
for (int i = 0 ; i < events.size() ; i++) {
if (events[i].second == 1) {
topdate_line(events[i].first.y, 1);
}
else if (events[i].second == 2) {
topdate_line(events[i].first.y, -1);
}
else {
int bottom = events[i++].first.y;
int top = events[i].first.y;
i_points += query(top) - query(bottom);
}
}
return i_points;
}
int calc_triangles() {
int points = calc_i_points();
if ( points >= 3 )
return ( points * (points - 1) * (points - 2) ) / 6;
else
return 0;
}
int main() {
insertLine(i_point(3, 2), i_point(3, 13));
insertLine(i_point(1, 5), i_point(3, 5));
insertLine(i_point(8, 2), i_point(8, 8));
insertLine(i_point(3, 4), i_point(6, 4));
insertLine(i_point(4, 3), i_point(4, 5));
sort(events.begin(), events.end(), com_points);
cout << "Possible number of triangles : " << calc_triangles() << endl;
return 0;
} आउटपुट
Possible number of triangles : 1