C++ प्रोग्राम: क्षैतिज और ऊर्ध्वाधर रेखा खंडों के बीच त्रिभुजों की संख्या ज्ञात करना

इस लेख में, हम एक प्रोग्राम पर चर्चा करेंगे जो दिए गए क्षैतिज और ऊर्ध्वाधर रेखा खंडों के प्रतिच्छेदन बिंदुओं को जोड़कर बनने वाले त्रिभुजों की संख्या ज्ञात करता है।

उदाहरण के लिए, मान लीजिए हमें निम्नलिखित रेखा खंड दिए गए हैं। इसमें हमारे पास 3 प्रतिच्छेदन बिंदु हैं। तो इन बिंदुओं का उपयोग करके बनने वाले त्रिभुजों की संख्या ³C₂ होगी।

  | ---|--------|--
  |       |       |
  | --|---|       |
  |       |       |

हम स्वीप लाइन एल्गोरिदम का पालन करेंगे। हम सभी रेखा खंडों के मानों को संग्रहीत करेंगे और फिर जांचेंगे कि क्या एक रेखा के अंदर के बिंदु किसी अन्य रेखा के आंतरिक बिंदुओं से तुलना करते हैं। इस तरह हम दिए गए रेखा खंडों के लिए सभी प्रतिच्छेदन बिंदु प्राप्त कर सकते हैं और फिर विभिन्न संभावित संयोजनों का उपयोग करके संभावित त्रिभुजों की संख्या आसानी से ज्ञात कर सकते हैं।

उदाहरण

#include <bits/stdc++.h>
#define maxy 1000005
#define maxn 10005
using namespace std;

// प्रतिच्छेदन बिंदुओं को संग्रहीत करने के लिए
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;

// दिए गए बिंदुओं को सॉर्ट करने के लिए
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;
}

// एक रेखा खंड डालने के लिए
void insertLine(i_point a, i_point b) {
    // क्षैतिज रेखा के मामले में
    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));
    }
    // ऊर्ध्वाधर रेखा के मामले में
    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));
    }
}

// प्रतिच्छेदन बिंदुओं की संख्या की गणना करने के लिए
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