C++ প্রোগ্রাম: হরিজন্টাল ও ভার্টিক্যাল লাইন সেগমেন্ট থেকে ত্রিভুজ গণনা

হরিজন্টাল ও ভার্টিক্যাল লাইন সেগমেন্টের ইন্টারসেকশন পয়েন্ট দিয়ে কতগুলো ত্রিভুজ বানানো যায়, সেটি বের করতে হবে। Sweep Line Algorithm + BIT (Fenwick Tree) ব্যবহার করা হয়।

অ্যালগরিদম

সব লাইন সেগমেন্ট স্টোর করুন (হরিজন্টাল: শুরু/শেষ, ভার্টিক্যাল: উপরের/নিচের y)।
ইভেন্ট সোর্ট করুন (x-কোঅর্ডিনেট অনুযায়ী)।
BIT দিয়ে হরিজন্টাল লাইন এক্টিভ রাখুন।
ভার্টিক্যাল লাইন পেলে BIT কোয়েরি করুন ইন্টারসেকশন কাউন্ট।
মোট ইন্টারসেকশন পয়েন্ট = P, ত্রিভুজ = ^PC₃।

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;
    return a.second < b.second;
}

void update(int idx, int val) {
    while (idx < maxn) { bit[idx] += val; idx += idx & -idx; }
}

int query(int idx) {
    int res = 0;
    while (idx > 0) { res += bit[idx]; idx -= idx & -idx; }
    return res;
}

void insertLine(i_point a, i_point b) {
    if (a.y == b.y) { // Horizontal
        int l = min(a.x, b.x), r = max(a.x, b.x);
        events.push_back({i_point(l, a.y), 1}); // start
        events.push_back({i_point(r, a.y), 2}); // end
    } else { // Vertical
        int top = max(a.y, b.y), bot = min(a.y, b.y);
        events.push_back({i_point(a.x, top), 3});
        events.push_back({i_point(a.x, bot), 3});
    }
}

int calc_intersections() {
    int cnt = 0;
    for (size_t i = 0; i < events.size(); i++) {
        if (events[i].second == 1) update(events[i].first.y, 1);
        else if (events[i].second == 2) update(events[i].first.y, -1);
        else {
            int bot = events[i++].first.y;
            int top = events[i].first.y;
            cnt += query(top) - query(bot);
        }
    }
    return cnt;
}

int calc_triangles() {
    int p = calc_intersections();
    return (p >= 3) ? (p*(p-1)*(p-2))/6 : 0;
}

int main() {
    insertLine({3,2}, {3,13});
    insertLine({1,5}, {3,5});
    insertLine({8,2}, {8,8});
    insertLine({3,4}, {6,4});
    insertLine({4,3}, {4,5});
    sort(events.begin(), events.end(), com_points);
    cout << "Possible number of triangles : " << calc_triangles() << endl;
    return 0;
}

আউটপুট

Possible number of triangles : 1