Approach
Our approach is to find how many vertical line segments intersect the horizontal line segments. So we divide each point into three parts
1. Horizontal line segment left point
2. Horizontal line segment right point
3. Vertical segment
Sorting
So we store the point and the tag in the event_array. Now we want to sort the array based on the x coordinate first. If the x coordinate is the same, we take
horizontal_left point, vertical line, and horizontal right line. If the event is also the same, we sort them by their y coordinate.
The idea behind this sorting is to know the information about the horizontal left points that have not ended whenever we are at the vertical line segment.
In the get_intersection function, when we encounter the horizontal segment left point, we update the bit_array for the y coordinate with 1. So can know in the future vertical line segments. Similarly, when we come across a horizontal segment right point, we update the bit_array for that y coordinate with -1 marking an end.
Counting Triangles
The number of triangles will be (intersections x (intersections-1) x (intersections-2)) /6.
The reason is that every three points will make a triangle as we are also counting triangles with 0 areas.
Thus the total number of triangles are intersectionsC3 which is equal to (intersections x (intersections-1) x (intersections-2)) /6
Code in C++
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
int maxy = 1e6 + 10;
vector<int> bit_array(maxy);
vector<pair<pii, int>> event_array;
/*
horizontal_left point is given value 1
horizontal_right point is given value 2
vertical line point is given value 3
values are given for differentiation purpose only
*/
int horizontal_left = 1;
int horizontal_right = 2;
int vertical = 3;
bool comparator_function(pair<pii, int> &a, pair<pii, int> &b)
{
/*
In this comparator function we aim to sort by
1. x coordinate
2. if x coordinate is same then we sort by horizontal_left point, then vertical line and then horizontal right line
*/
if (a.first.first != b.first.first)
{
// if the x coordinate is different then sort by x coordinate
return a.first.first < b.first.first;
}
// if the are same line i.e. a.second==b.second then we return based on the y coordinate
// i.e. we return a.first < b.first and since a.first.first and b.first.first are same thery are returned by the y coordinate
if (a.second == b.second)
{
return a.first<b.first;
}
/* if a.second=vertical this means that a.second is a vertical line point
and b.second is horizontal left point ;
Then from the second point we have to swap them
*/
if (a.second == vertical and b.second == horizontal_left)
{
return 0;
}
/* if a.second=horizontal right this means that a.second is a horizontal right point
and b.second is vertical line point ;
Then from the second point in comparison rule we have to swap them
*/
if (a.second == horizontal_right and b.second == vertical)
{
return 0;
}
/*
In all other cases we do not have to swap
so we return 1
*/
return 1;
}
void update(int index, int value)
{
// update the value at index
while (index < bit_array.size())
{
bit_array[index] += value;
index += index & (-index);
}
}
int query(int index)
{
/* query the value at index returns the prefix sum
i.e. it returns the count of points having y coordinate between 1 and index
*/
int sum = 0;
while (index > 0)
{
sum += bit_array[index];
index -= index & (-index);
}
return sum;
}
void add_event(pii a, pii b)
{
// if the y coordinate i.e. a.second= b.second
if (a.second == b.second)
{
// we swap if a is bigger than b
if (a > b)
{
swap(a, b);
}
// as a has lower x coordinate we add horizontal_left with a
event_array.push_back({a, horizontal_left});
event_array.push_back({b, horizontal_right});
}
else
{
// as a and b have same x coordinate they are vertical line
// so we add vertical tag with them
event_array.push_back({a, vertical});
event_array.push_back({b, vertical});
}
}
int get_intersections()
{
int intersections = 0;
for (int i = 0; i < event_array.size(); ++i)
{
if (event_array[i].second == horizontal_left)
{
update(event_array[i].first.second, 1);
}
else if (event_array[i].second == horizontal_right)
{
update(event_array[i].first.second, -1);
}
else if (event_array[i].second == vertical)
{
int now = event_array[i].first.second;
int next = event_array[i+1].first.second;
// cout << query(now) << " " << query(next) << endl;
// cout << now << " " << next << endl;
intersections += query(next) - query(now);
i += 1;
}
// for(int i=0;i<10;++i){
// cout<<bit_array[i]<< " ";
// }
// cout<<endl;
// cout << intersections << endl;
}
return intersections;
}
int main()
{
int no_of_lines = 6;
vector<vector<pii>> lines(no_of_lines);
lines[0] = {{2, 3}, {2, 9}};
lines[1] = {{1, 7}, {6, 7}};
lines[2] = {{4, 9}, {4, 18}};
lines[3] = {{3, 4}, {6, 4}};
lines[4] = {{4, 3}, {4, 15}};
lines[5] = {{3, 6}, {3, 16}};
// for(auto i:lines)
// {
// for(auto j:i){
// cout<<j.first<<" "<<j.second<<endl;
// }
// }
for (auto i : lines)
{
add_event(i[0], i[1]);
}
sort(event_array.begin(), event_array.end(), comparator_function);
// for (auto i : event_array)
// {
// cout << i.first.first << " " << i.first.second << " " << i.second << endl;
// }
int intersections = get_intersections();
int triangles = (intersections * (intersections - 1) * (intersections - 2)) / 6;
cout << triangles << endl;
}
You can also try this code with Online C++ Compiler
Output
4
Time Complexity
First, we are calling the add_event N times. Thus the time for it is O(N).
Then we are sorting N lines using the comparator function. The comparator function takes O(1) time, and so the sorting with comparator takes O(N x log(N)).
We are using the bit vector of size max_y. There are 2 x N updates, and 2 x (2 x N) queries.
Thus the time for this is O(N x log(max_y_coordinate)).
The time complexity of the above program is O( N x log(N) + N x log(max_y_coordinate)).
Space Complexity
Here we are making a BIT array of size max_y_coordinate.
Another array of lines of size N stores the lines' points.
Similarly, another array of events of size N also stores the points.
Thus the space complexity of the above code is O(max_y_coordinate+N)
Frequently Asked Questions
1. What is the comparator function used in the code?
The comparator function is used to compare two indices of the vector. While comparing two indices, the program uses the comparator function to swap the indices. Thus, we can sort the array according to our priority using the comparator function.
2. What would be the time complexity of the naive algorithm?
In the naive algorithm, we would check whether each horizontal line intersects with the vertical line. Each check would take O(1) time. If half of the lines are horizontal, there are O(N) horizontal and vertical lines. Thus checking each horizontal line with the vertical line would take O(N x N) time. The space complexity would be O(N) as we are not making the BIT array.
3. Why are we sorting by the specific tag in the algorithm?
Here we are sorting by Horizontal left, vertical line, and horizontal right if the x coordinate is the same. The idea behind this sorting is that whenever we are at the vertical line segment, we can know the information about the horizontal left points has been so far. Thus we can estimate how many horizontal segments the vertical line will intersect. Similarly, after encountering the horizontal segment right point, we know that the horizontal left segment has ended.
Key Takeaways
The article helps us understand the use of the Fenwick tree to calculate the number of triangles among intersecting lines. You can also uncomment the print statements to see different arrays. Comments have been added to the code for better understanding. You can also copy the code and run it on your system on multiple inputs to understand the approach better.
Check out the following problems -
Check out Coding Ninjas Studio to learn more about competitive programming, DSA, attempt mock tests, interview preparation and much more.
Happy Learning!!!
84+ registered