Trong bài viết này, chúng ta sẽ thảo luận về một chương trình để tìm số lượng tam giác có thể được tạo thành bằng cách nối các giao điểm của các đoạn thẳng đứng và ngang đã cho.
Ví dụ:giả sử chúng tôi đã được cung cấp các phân đoạn dòng sau. Trong này chúng ta có 3 điểm giao nhau. Vì vậy, số tam giác có thể được tạo thành bằng cách sử dụng các điểm này sẽ là 3 C 2 .
| ---|--------|-- | | | --|---| | |
Chúng ta sẽ theo dõi Thuật toán dòng quét. Chúng tôi sẽ lưu trữ tất cả các giá trị của các đoạn thẳng và sau đó kiểm tra xem các điểm bên trong một đoạn thẳng có so sánh với các điểm bên trong của bất kỳ đoạn thẳng nào khác hay không. Bằng cách này, chúng ta có thể có tất cả các giao điểm của các đoạn thẳng đã cho và sau đó chúng ta có thể dễ dàng tìm thấy số lượng tam giác có thể có bằng cách sử dụng các kết hợp có thể có khác nhau.
Ví dụ
#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;
} Đầu ra
Possible number of triangles : 1