ในบทความนี้ เราจะพูดถึงโปรแกรมเพื่อหาจำนวนสามเหลี่ยมที่สามารถเกิดขึ้นได้โดยการรวมจุดตัดกันของส่วนของเส้นแนวนอนและแนวตั้งที่กำหนด
ตัวอย่างเช่น สมมติว่าเราได้รับส่วนของเส้นตรงต่อไปนี้ ในนี้เรามีจุดตัดกัน 3 จุด ดังนั้นจำนวนสามเหลี่ยมที่สามารถเกิดขึ้นได้โดยใช้จุดเหล่านี้จะเป็น 3 C2 .
| ---|--------|-- | | | --|---| | |
เราจะทำตามอัลกอริธึม Sweep Line เราจะจัดเก็บค่าทั้งหมดของส่วนของเส้นตรง จากนั้นตรวจสอบว่าจุดภายในเส้นใดเส้นหนึ่งนั้นเปรียบเทียบกับจุดภายในของเส้นอื่นๆ หรือไม่ ด้วยวิธีนี้ เราจะมีจุดตัดกันทั้งหมดสำหรับส่วนของเส้นตรงที่กำหนด จากนั้นเราสามารถหาจำนวนสามเหลี่ยมที่เป็นไปได้ได้อย่างง่ายดายโดยใช้ชุดค่าผสมต่างๆ ที่เป็นไปได้
ตัวอย่าง
#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
