Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Sorting
3.2.
Counting Triangles
4.
Code in C++
4.1.
Time Complexity
4.2.
Space Complexity
5.
Frequently Asked Questions
6.
Key Takeaways
Last Updated: Mar 27, 2024

Finding the number of triangles amongst horizontal and vertical line segments

Author HET FADIA
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

This article aims to familiarise you with the use of the Fenwick tree(Binary Indexed Tree) to calculate the number of triangles among intersecting lines. 

To brush up on your knowledge of binary indexed trees, you can read the article Binary Indexed Tree on Coding Ninjas Studio.

Let’s see the problem statement in the next section.

Problem Statement

There are N lines segments given in a plane. Each line segment is either horizontal or vertical. We have to find the number of triangles (even with the 0 areas) formed by the intersecting points of these lines. Here the two endpoints of the line segment are given to represent the line segment.

Also, any two lines do not overlap on more than one point. Thus no horizontal line overlaps with another horizontal line, and no vertical line overlaps another vertical line. A horizontal line may or may not intersect a vertical line.

Input Style: The first line of input contains n. In the following n lines, 4 integers are given. The first two integers give us the first point of the lines, and the last two integers give us the following two points.

Output Style: Output the number of triangles formed by the intersecting points of these lines.

Note: We will use “BIT” as a short form for the Binary Indexed Tree throughout the article. The other name of BIT is Fenwick tree.

Let us look at some examples

Input

4

0 0 0 8 

0 0 8 0

0 8 8 8

8 0 8 8

Output

4

Explanation:

The first line segment is represented by {0,0} and {0,8} points.

Thus it is a horizontal line segment.

The second line segment is represented by {0,0} and {8,0} points. Thus it is a vertical line segment

Similarly, the third line segment is horizontal, and the 4th one is vertical.

These line segments intersect at {0,0} , {0,8}, {8,0} and {8,8} as seen in the below figure.

Figure 1: Shows the intersection points of the lines

 

Thus the number of triangles = 4C3 = 4 triangles.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 intersectionsCwhich 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;
}

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!!!
 

Previous article
Count Number of Intersection Points for Given Lines Between (i, 0) and (j, 1)
Next article
Average Value of Set Bit Count in Given Binary String after Performing All Possible Choices of M Operations
Live masterclass