|
Given an array, lines[] of N pairs of the form (i, j) where (i, j) represents a line segment from coordinate (i, 0) to (j, 1), the task is to find the count of points of intersection of the given lines.
Example:
Input: lines[] = {{1, 2}, {2, 1}}
Output: 1
Explanation: For the given two pairs, the line form (1, 0) to (2, 1) intersect with the line from (2, 0) to (1, 1) at point (1.5, 0.5). Hence the total count of points of intersection is 1.
Input: lines[] = {{1, 5}, {2, 1}, {3, 7}, {4, 1}, {8, 2}}
Output: 5
Approach: The given problem can be solved using a Greedy approach using the policy-based data structure. It can be observed that for lines represented b two pairs (a, b) and (c, d) to intersect either (a > c and b < d) or (a < c and b > d) must hold true.
Therefore using this observation, the given array of pairs can be sorted in decreasing order of the 1st element. While traversing the array, insert the value of the second element into the policy-based data structure and find the count of elements smaller than the second element of the inserted pair using the order_of_key function and maintain the sum of count in a variable. Similarly, calculate for the cases after sorting the given array of pairs in decreasing order of their 2nd element.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type,
less_equal<int>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_multiset;
int cntIntersections(
vector<pair<int, int> > lines,
int N)
{
int cnt = 0;
ordered_multiset s;
for (int i = 0; i < N; i++) {
cnt += s.order_of_key(lines[i].second);
s.insert(lines[i].second);
}
return cnt;
}
int cntAllIntersections(
vector<pair<int, int> > lines,
int N)
{
sort(lines.begin(), lines.end(),
greater<pair<int, int> >());
int totalCnt = 0;
totalCnt += cntIntersections(lines, N);
for (int i = 0; i < N; i++) {
swap(lines[i].first, lines[i].second);
}
totalCnt += cntIntersections(lines, N);
return totalCnt;
}
int main()
{
vector<pair<int, int> > lines{
{1, 5}, {2, 1}, {3, 7}, {4, 1}, {8, 2}
};
cout << cntAllIntersections(lines,
lines.size());
return 0;
}
|
Java
import java.io.*;
import java.lang.*;
import java.util.*;
import java.util.TreeSet;
import java.util.function.*;
class Main {
static int cntIntersections(Pair[] lines, int N)
{
int cnt = 0;
TreeSet<Integer> s = new TreeSet<Integer>();
for (int i = 0; i < N; i++) {
cnt += s.headSet(lines[i].b, true).size();
s.add(lines[i].b);
}
return cnt;
}
static int cntAllIntersections(Pair[] lines, int N)
{
Arrays.sort(lines, new Comparator<Pair>() {
public int compare(Pair p1, Pair p2)
{
if (p1.a == p2.a) {
return p1.b - p2.b;
}
return p2.a - p1.a;
}
});
int totalCnt = 0;
totalCnt += cntIntersections(lines, N);
for (int i = 0; i < N; i++) {
int temp = lines[i].a;
lines[i].a = lines[i].b;
lines[i].b = temp;
}
totalCnt += cntIntersections(lines, N);
return totalCnt;
}
public static void main(String[] args)
{
Pair[] lines = { new Pair(1, 5), new Pair(2, 1),
new Pair(3, 7), new Pair(4, 1),
new Pair(8, 2) };
System.out.println(
cntAllIntersections(lines, lines.length));
}
static class Pair {
int a, b;
Pair(int a, int b)
{
this.a = a;
this.b = b;
}
}
}
|
Python3
from bisect import *
def cntIntersections(lines, N):
cnt = 0
s = []
for i in range(N):
cnt += bisect_left(s, lines[i][1])
s.append(lines[i][1])
s.sort()
return cnt
def cntAllIntersections(lines, N):
lines = sorted(lines, reverse=True)
totalCnt = 0
totalCnt += cntIntersections(lines, N)
lines = [(b, a) for (a, b) in lines]
totalCnt += cntIntersections(lines, N)
return totalCnt
if __name__ == '__main__':
lines = [(1, 5), (2, 1), (3, 7), (4, 1), (8, 2)]
print(cntAllIntersections(lines, len(lines)))
|
C#
using System;
using System.Collections.Generic;
public class Program {
static int cntIntersections(Pair[] lines, int N)
{
int cnt = 0;
SortedSet<int> s = new SortedSet<int>();
for (int i = 0; i < N; i++) {
cnt += s.GetViewBetween(int.MinValue,
lines[i].b)
.Count;
s.Add(lines[i].b);
}
return cnt;
}
static int cntAllIntersections(Pair[] lines, int N)
{
Array.Sort(lines, new PairComparer());
int totalCnt = 0;
totalCnt += cntIntersections(lines, N);
for (int i = 0; i < N; i++) {
int temp = lines[i].a;
lines[i].a = lines[i].b;
lines[i].b = temp;
}
totalCnt += cntIntersections(lines, N);
return totalCnt;
}
public static void Main()
{
Pair[] lines = { new Pair(1, 5), new Pair(2, 1),
new Pair(3, 7), new Pair(4, 1),
new Pair(8, 2) };
Console.WriteLine(
cntAllIntersections(lines, lines.Length));
}
public class Pair {
public int a, b;
public Pair(int a, int b)
{
this.a = a;
this.b = b;
}
}
public class PairComparer : IComparer<Pair> {
public int Compare(Pair p1, Pair p2)
{
if (p1.a == p2.a) {
return p1.b - p2.b;
}
return p2.a - p1.a;
}
}
}
|
Javascript
function cntIntersections(lines, N) {
let cnt = 0;
let s = [];
for (let i = 0; i < N; i++) {
cnt += s.filter(x => x < lines[i][1]).length;
s.push(lines[i][1]);
s.sort((a, b) => a - b);
}
return cnt;
}
function cntAllIntersections(lines, N) {
lines = lines.sort((a, b) => b[0] - a[0]);
let totalCnt = 0;
totalCnt += cntIntersections(lines, N);
lines = lines.map(x => [x[1], x[0]]);
totalCnt += cntIntersections(lines, N);
return totalCnt;
}
let lines = [[1, 5], [2, 1], [3, 7], [4, 1], [8, 2]];
console.log(cntAllIntersections(lines, lines.length));
|
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
|
