โปรแกรม C++ หาจำนวนสามเหลี่ยมจากจุดตัดของเส้นแนวนอนและแนวตั้ง

หาจำนวนสามเหลี่ยมที่สร้างจากจุดตัดของเส้นแนวนอนและแนวตั้งที่กำหนด

ใช้ Sweep Line Algorithm เก็บค่าเส้นทั้งหมด ตรวจสอบจุดตัดระหว่างเส้นแนวนอนและแนวตั้ง แล้วคำนวณจำนวนสามเหลี่ยมจากจุดตัด (nC3)

ตัวอย่างโค้ด

#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) { // horizontal
        int begin = min(a.x, b.x), 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 { // vertical
        int top = max(b.y, a.y), 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