Dadas las coordenadas x de N líneas verticales (paralelas al eje Y) y M segmentos de línea que se extienden desde (x1, y1) a (x2, y2), la tarea es encontrar el número total de intersecciones de los segmentos de línea con las líneas verticales .
Ejemplos:
Entrada: N = 2, M = 1, líneas[] = {-1, 1}, Segmentos[][4] = {0, 1, 2, 1}
Salida: 1
Explicación:
Solo hay un punto de intersección ( 1, 1)
Entrada: N = 4, M = 8, líneas[] = {-5, -3, 2, 3}, segmentos[][4] = {{-2, 5, 5, -6}, {-5, -2, -3, -5}, {-2, 3, -6, 1}, {-1, -3, 4, 2}, {2, 5, 2, 1}, {4, 5, 4 , -5}, {-2, -4, 5, 3}, {1, 2, -2, 1}};
Salida: 8
Explicación:
Hay un total de 8 intersecciones.
Las líneas punteadas son las líneas verticales.
Un círculo verde denota un solo punto de intersección y
un triángulo verde denota que dos segmentos de línea se
cruzan con la misma línea vertical en ese punto.
Enfoque ingenuo:
el enfoque más simple es, para cada consulta, verificar si una línea vertical se encuentra entre las coordenadas x de los dos puntos. Así, cada segmento tendrá una complejidad computacional O(N).
Complejidad de tiempo: O(N * M)
Enfoque 2: La idea es usar Prefix Sum para resolver este problema de manera eficiente. Siga los pasos a continuación para resolver el problema:
- La primera observación que podemos hacer es que las coordenadas y no importan. Además, podemos observar que solo tocar la línea vertical no cuenta como una intersección.
- Primero, calcule una array de prefijos del número de ocurrencias de líneas verticales hasta ahora y luego simplemente reste el número de ocurrencias hasta x2-1 (no consideramos x2 ya que solo califica como toque y no como una intersección) del número de ocurrencias hasta x1 . Entonces, para cada segmento, la complejidad computacional se reduce a O(1) .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation for the
// above approach.
#include <bits/stdc++.h>
using namespace std;
// Function to create prefix sum array
void createPrefixArray(int n, int arr[],
int prefSize,
int pref[])
{
// Initialize the prefix array
// to remove garbage values
for (int i = 0; i < prefSize; i++) {
pref[i] = 0;
}
// Marking the occurrences of
// vertical lines
for (int i = 0; i < n; i++) {
// x is the value after
// Index mapping
int x = arr[i] + 1000000;
pref[x]++;
}
// Creating the prefix array
for (int i = 1; i < prefSize; i++) {
pref[i] += pref[i - 1];
}
}
// Function returns the count of
// total intersection
int pointsOfIntersection(int m,
int segments[][4],
int size,
int pref[])
{
// ans is the number of points of
// intersection of the line segments
// with the vertical lines
int ans = 0;
for (int i = 0; i < m; i++) {
int x1 = segments[i][0];
int x2 = segments[i][2];
// Index mapping
x1 = x1 + 1000000;
x2 = x2 + 1000000;
// We don't consider a vertical
// line segment because even if
// it falls on a vertical line
// then it just touches it and
// not intersects.
if (x1 != x2) {
// We have assumed that x1
// will be left and x2 right
// but if not then we just
// swap them
if (x1 > x2) {
swap(x1, x2);
}
int Occ_Till_Right = pref[x2 - 1];
int Occ_Till_Left = pref[x1];
ans = ans + (Occ_Till_Right
- Occ_Till_Left);
}
}
return ans;
}
int main()
{
// N is the number of vertical lines
// M is the number of line segments
int N = 4;
int M = 8;
int size = 2000000 + 2;
int pref[size];
int lines[N] = { -5, -3, 2, 3 };
// Format : x1, y1, x2, y1
int segments[M][4] = { { -2, 5, 5, -6 },
{ -5, -2, -3, -5 },
{ -2, 3, -6, 1 },
{ -1, -3, 4, 2 },
{ 2, 5, 2, 1 },
{ 4, 5, 4, -5 },
{ -2, -4, 5, 3 },
{ 1, 2, -2, 1 } };
// First create the prefix array
createPrefixArray(N, lines, size, pref);
// Print the total number of intersections
cout << pointsOfIntersection(M, segments,
size, pref)
<< endl;
return 0;
}
Java
// Java implementation for the
// above approach.
import java.util.*;
class GFG{
// Function to create prefix sum array
static void createPrefixArray(int n, int arr[],
int prefSize,
int pref[])
{
// Initialize the prefix array
// to remove garbage values
for(int i = 0; i < prefSize; i++)
{
pref[i] = 0;
}
// Marking the occurrences of
// vertical lines
for(int i = 0; i < n; i++)
{
// x is the value after
// Index mapping
int x = arr[i] + 1000000;
pref[x]++;
}
// Creating the prefix array
for(int i = 1; i < prefSize; i++)
{
pref[i] += pref[i - 1];
}
}
// Function returns the count of
// total intersection
static int pointsOfIntersection(int m,
int segments[][],
int size,
int pref[])
{
// ans is the number of points of
// intersection of the line segments
// with the vertical lines
int ans = 0;
for(int i = 0; i < m; i++)
{
int x1 = segments[i][0];
int x2 = segments[i][2];
// Index mapping
x1 = x1 + 1000000;
x2 = x2 + 1000000;
// We don't consider a vertical
// line segment because even if
// it falls on a vertical line
// then it just touches it and
// not intersects.
if (x1 != x2)
{
// We have assumed that x1
// will be left and x2 right
// but if not then we just
// swap them
if (x1 > x2)
{
int temp = x1;
x1 = x2;
x2 = temp;
}
int Occ_Till_Right = pref[x2 - 1];
int Occ_Till_Left = pref[x1];
ans = ans + (Occ_Till_Right -
Occ_Till_Left);
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
// N is the number of vertical lines
// M is the number of line segments
int N = 4;
int M = 8;
int size = 2000000 + 2;
int []pref = new int[size];
int lines[] = { -5, -3, 2, 3 };
// Format : x1, y1, x2, y1
int segments[][] = { { -2, 5, 5, -6 },
{ -5, -2, -3, -5 },
{ -2, 3, -6, 1 },
{ -1, -3, 4, 2 },
{ 2, 5, 2, 1 },
{ 4, 5, 4, -5 },
{ -2, -4, 5, 3 },
{ 1, 2, -2, 1 } };
// First create the prefix array
createPrefixArray(N, lines, size, pref);
// Print the total number of intersections
System.out.print(pointsOfIntersection(M, segments,
size, pref) + "\n");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 implementation for the # above approach # Function to create prefix sum array def createPrefixArray(n, arr, prefSize, pref): # Initialize the prefix array # to remove garbage values for i in range(prefSize): pref[i] = 0 # Marking the occurrences # of vertical lines for i in range(n): x = arr[i] + 1000000 pref[x] += 1 # Creating the prefix array for i in range(1, prefSize): pref[i] += pref[i - 1] # Function that returns the count # of total intersection def pointOfIntersection(m, segments, size, pref): # ans is the number of points of # intersection of the line segments # with the vertical lines ans = 0 for i in range(m): x1 = segments[i][0] x2 = segments[i][2] # Index mapping x1 = x1 + 1000000 x2 = x2 + 1000000 # we don't consider a vertical # line segment because even if # it falls on a vertical line # then it just touches it and # not intersects. if (x1 != x2): # We have assumed that x1 # will be left and x2 right # but if not then just swap if (x1 > x2): x1, x2 = x2, x1 Occ_Till_Right = pref[x2 - 1] Occ_Till_Left = pref[x1] ans += (Occ_Till_Right - Occ_Till_Left) return ans # Driver code # Number of vertical lines N = 4 # Number of line segments M = 8 size = 2000000 + 2 pref = [0] * size lines = [ -5, -3, 2, 3 ] # Format : x1, y1, x2, y2 segments = [ [ -2, 5, 5, -6 ], [ -5, -2, -3, -5 ], [ -2, 3, -6, 1 ], [ -1, -3, 4, 2 ], [ 2, 5, 2, 1 ], [ 4, 5, 4, -5 ], [ -2, -4, 5, 3 ], [ 1, 2, -2, 1 ] ] # First create the prefix array createPrefixArray(N, lines, size, pref) # Print the total number of intersections print(pointOfIntersection(M, segments, size, pref)) # This code is contributed by himanshu77
C#
// C# implementation for the
// above approach.
using System;
class GFG{
// Function to create prefix sum array
static void createPrefixArray(int n, int []arr,
int prefSize,
int []pref)
{
// Initialize the prefix array
// to remove garbage values
for(int i = 0; i < prefSize; i++)
{
pref[i] = 0;
}
// Marking the occurrences of
// vertical lines
for(int i = 0; i < n; i++)
{
// x is the value after
// Index mapping
int x = arr[i] + 1000000;
pref[x]++;
}
// Creating the prefix array
for(int i = 1; i < prefSize; i++)
{
pref[i] += pref[i - 1];
}
}
// Function returns the count of
// total intersection
static int pointsOfIntersection(int m,
int [,]segments,
int size,
int []pref)
{
// ans is the number of points of
// intersection of the line segments
// with the vertical lines
int ans = 0;
for(int i = 0; i < m; i++)
{
int x1 = segments[i, 0];
int x2 = segments[i, 2];
// Index mapping
x1 = x1 + 1000000;
x2 = x2 + 1000000;
// We don't consider a vertical
// line segment because even if
// it falls on a vertical line
// then it just touches it and
// not intersects.
if (x1 != x2)
{
// We have assumed that x1
// will be left and x2 right
// but if not then we just
// swap them
if (x1 > x2)
{
int temp = x1;
x1 = x2;
x2 = temp;
}
int Occ_Till_Right = pref[x2 - 1];
int Occ_Till_Left = pref[x1];
ans = ans + (Occ_Till_Right -
Occ_Till_Left);
}
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
// N is the number of vertical lines
// M is the number of line segments
int N = 4;
int M = 8;
int size = 2000000 + 2;
int []pref = new int[size];
int []lines = { -5, -3, 2, 3 };
// Format : x1, y1, x2, y1
int [,]segments = { { -2, 5, 5, -6 },
{ -5, -2, -3, -5 },
{ -2, 3, -6, 1 },
{ -1, -3, 4, 2 },
{ 2, 5, 2, 1 },
{ 4, 5, 4, -5 },
{ -2, -4, 5, 3 },
{ 1, 2, -2, 1 } };
// First create the prefix array
createPrefixArray(N, lines, size, pref);
// Print the total number of intersections
Console.Write(pointsOfIntersection(M, segments,
size, pref) + "\n");
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript implementation of the
// above approach
// Function to create prefix sum array
function createPrefixArray(n, arr, prefSize, pref)
{
// Initialize the prefix array
// to remove garbage values
for(let i = 0; i < prefSize; i++)
{
pref[i] = 0;
}
// Marking the occurrences of
// vertical lines
for(let i = 0; i < n; i++)
{
// x is the value after
// Index mapping
let x = arr[i] + 1000000;
pref[x]++;
}
// Creating the prefix array
for(let i = 1; i < prefSize; i++)
{
pref[i] += pref[i - 1];
}
}
// Function returns the count of
// total intersection
function pointsOfIntersection(m, segments,
size, pref)
{
// ans is the number of points of
// intersection of the line segments
// with the vertical lines
let ans = 0;
for(let i = 0; i < m; i++)
{
let x1 = segments[i][0];
let x2 = segments[i][2];
// Index mapping
x1 = x1 + 1000000;
x2 = x2 + 1000000;
// We don't consider a vertical
// line segment because even if
// it falls on a vertical line
// then it just touches it and
// not intersects.
if (x1 != x2)
{
// We have assumed that x1
// will be left and x2 right
// but if not then we just
// swap them
if (x1 > x2)
{
let temp = x1;
x1 = x2;
x2 = temp;
}
let Occ_Till_Right = pref[x2 - 1];
let Occ_Till_Left = pref[x1];
ans = ans + (Occ_Till_Right -
Occ_Till_Left);
}
}
return ans;
}
// Driver Code
// N is the number of vertical lines
// M is the number of line segments
let N = 4;
let M = 8;
let size = 2000000 + 2;
let pref = Array.from({length: size}, (_, i) => 0);
let lines = [ -5, -3, 2, 3 ];
// Format : x1, y1, x2, y1
let segments = [ [ -2, 5, 5, -6 ],
[ -5, -2, -3, -5 ],
[ -2, 3, -6, 1 ],
[ -1, -3, 4, 2 ],
[ 2, 5, 2, 1 ],
[ 4, 5, 4, -5 ],
[ -2, -4, 5, 3 ],
[ 1, 2, -2, 1 ] ];
// First create the prefix array
createPrefixArray(N, lines, size, pref);
// Print the total number of intersections
document.write(pointsOfIntersection(M, segments,
size, pref) + "\n");
// This code is contributed by sanjoy_62
</script>
Producción:
8
Enfoque 3: Para optimizar el enfoque anterior, podemos adoptar un método eficiente en el espacio usando la estructura Map Data . Siga los pasos a continuación para resolver el problema:
- Podemos hacer un mapa que almacene el número de ocurrencias hasta ahora, solo que la diferencia con el primer enfoque es que insertamos solo las coordenadas que tienen las líneas verticales.
- Cuando queremos buscar el número de intersecciones de x1 a x2, podemos simplemente restar el límite inferior (x1 + 1) del límite superior (x2-1) del mapa.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation for the
// above approach.
#include <bits/stdc++.h>
using namespace std;
// Function to create map that stores
// the number of occurrences of the
// vertical lines till now.
map<int, int> createMap(int n,
int arr[])
{
map<int, int> mp;
sort(arr, arr + n);
for (int i = 0; i < n; i++) {
mp.insert({ arr[i], i + 1 });
}
return mp;
}
// Function returns the count of
// total intersections
int pointsOfIntersection(int m,
int segments[][4],
int n,
map<int, int> pref)
{
// ans stores the number
// of intersections
int ans = 0;
// Loop over all the segments
for (int i = 0; i < m; i++) {
int x1 = segments[i][0];
int x2 = segments[i][2];
if (x1 == x2) {
continue;
}
// For convenience we make x1 as
// x co-ordinate of left point
// and x2 as x co-ordinate of
// right point.
if (x1 > x2) {
swap(x1, x2);
}
auto it1 = *pref.lower_bound(x1 + 1);
auto it2 = *pref.upper_bound(x2 - 1);
int intersections = 0;
// If x co-ordinate of the left point
// is after the last vertical line
// then we dont add anything.
if (pref.lower_bound(x1 + 1)
== pref.end()) {
intersections = 0;
}
// If there is no occurrence of any
// vertical line after (x2-1)
// then we can mark the
// number of intersections as
// n - occurrences till x1
// because the total occurrences
// are n and all of them
// will fall before x2.
else if (pref.upper_bound(x2 - 1)
== pref.end()) {
intersections
= n - it1.second + 1;
}
else {
intersections
= it2.second
- it1.second;
}
ans += intersections;
}
return ans;
}
// Driver code
int main()
{
// N is the number of vertical lines
// M is the number of line segments
int N = 4;
int M = 8;
int lines[N] = { -5, -3, 2, 3 };
// Format : x1, y1, x2, y1
int segments[M][4]
= { { -2, 5, 5, -6 },
{ -5, -2, -3, -5 },
{ -2, 3, -6, 1 },
{ -1, -3, 4, 2 },
{ 2, 5, 2, 1 },
{ 4, 5, 4, -5 },
{ -2, -4, 5, 3 },
{ 1, 2, -2, 1 } };
map<int, int> pref = createMap(N, lines);
cout << pointsOfIntersection(
M,
segments,
N, pref)
<< endl;
return 0;
}
Producción:
8
Publicación traducida automáticamente
Artículo escrito por gauravak007 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA