Dadas dos arrays de enteros, X e Y representan puntos en el plano XY. Calcula el número de pares de segmentos de línea que se intersecan formados a partir de cada posible par de coordenadas.
Ejemplo:
Entrada: X = [0, 1, 0, 1], Y = [0, 1, 3, 2]
Salida: 14
Explicación:
Para simplificar, denotemos A = [0, 0], B = [1, 1], C = [1, 2], D = [0, 3].
- El segmento de línea entre el punto (A, B) y el punto (A, C) se interseca.
- El segmento de línea entre el punto (A, B) y el punto (A, D) se interseca.
- El segmento de línea entre el punto (A, B) y el punto (B, D) se interseca.
- El segmento de línea entre el punto (A, B) y el punto (C, D) se interseca.
- El segmento de línea entre el punto (A, B) y el punto (B, C) se interseca.
- El segmento de línea entre el punto (A, C) y el punto (C, D) se interseca.
- El segmento de línea entre el punto (A, C) y el punto (B, D) se interseca
- El segmento de línea entre el punto (A, C) y el punto (A, D) se interseca.
- El segmento de línea entre el punto (A, C) y el punto (B, C) se interseca.
- El segmento de línea entre el punto (A, D) y el punto (B, D) se interseca.
- El segmento de línea entre el punto (A, D) y el punto (C, D) se interseca.
- El segmento de línea entre el punto (B, C) y el punto (B, D) se interseca.
- El segmento de línea entre el punto (B, C) y el punto (C, D) se interseca.
- El segmento de línea entre el punto (B, D) y el punto (C, D) se interseca.
Entrada: X = [0, 0, 0, 2], Y = [0, 2, 4, 0]
Salida: 6
Enfoque ingenuo:
- Almacene todos los pares de coordenadas en una estructura de datos.
- Para cada par de pares de coordenadas comprueba si son paralelas o no. Si no son paralelas, entonces esta línea debe intersecarse. Aumenta la respuesta en 1.
Complejidad del tiempo: O(N^4)
Enfoque eficiente:
- Para cada par de coordenadas, almacene estos parámetros (pendiente, intersección en el eje x o el eje y) de una línea.
- Para rectas paralelas al eje X:
- Pendiente = 0, Intersección = Y[i]
- Para rectas paralelas al eje Y:
- Pendiente = INF, Intersección = X[i]
- Para todas las demás líneas:
- Pendiente = (dy/dx = (y2 – y1)/(x2 – x1)
- Para calcular el intercepto, conocemos la forma general de una línea, es decir, y = (dy/dx)*x + c
- Poniendo y1 en lugar de y y x1 en lugar de x cuando la línea misma pasa por (x1, y1).
- Después del paso anterior, obtenemos Intercepción = (y1*dx – x1*dy)/dx
- Entonces, para cada línea, tenemos tres casos:
- Una recta puede tener la misma pendiente y el mismo intercepto que otra recta. Estas líneas no se intersecarán ya que son básicamente la misma línea.
- Una recta puede tener la misma pendiente y diferentes intersecciones con otra recta. Estas líneas tampoco se intersecarán ya que son paralelas.
- Una recta puede tener una pendiente diferente a la de otra recta. Estas líneas definitivamente se intersecarán independientemente de sus intersecciones .
- Almacene la frecuencia de las líneas con las mismas pendientes. Mantenga un mapa de acuerdo con las condiciones anteriores y fije un tipo de segmento de línea y calcule el número de segmentos de línea que se cruzan con las líneas restantes.
Nota:
En la siguiente implementación, hemos evitado el uso de dobles para evitar errores causados por errores de precisión.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate total pairs
// of intersecting lines
int totalPairsOfIntersectineLines(
int X[], int Y[], int N)
{
// Set to check the occurrences
// of slope and intercept
// It will store the slope dy/dx
// as {dy, dx} and intercept as {c1, c2}
set<pair<pair<int, int>, pair<int, int> > > st;
// Map to keep track of count of slopes
map<pair<int, int>, int> mp;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
// Numerator of the slope
int dx = X[j] - X[i];
// Denominator of the slope
int dy = Y[j] - Y[i];
// Making dx and dy coprime
// so that we do not repeat
int g = __gcd(dx, dy);
dx /= g, dy /= g;
// Checking for lines parallel to y axis
if (dx == 0) {
// Intercepts of the line
int c1, c2;
c1 = X[i];
c2 = INT_MAX;
// pair to check the previous occurrence of
// the line parameters
pair<pair<int, int>, pair<int, int> > pr
= { { dx, dy }, { c1, c2 } };
if (st.find(pr) != st.end()) {
// Do nothing as this line is same just
// an etenstion to some line with same
// slope and intercept
}
else {
// Insert this line to the set
st.insert(pr);
// increase the count of the slope of
// this line
mp[pr.first]++;
}
}
// Checking for lines parallel to x- axis
else if (dy == 0) {
int c1, c2;
c2 = Y[i];
c1 = INT_MAX;
pair<pair<int, int>, pair<int, int> > pr
= { { dx, dy }, { c1, c2 } };
if (st.find(pr) != st.end()) {
// Do nothing as this line is same just
// an etenstion to some line with same
// slope and intercept
}
else {
// Insert this line to the set
st.insert(pr);
// increase the count of the slope of
// this line
mp[pr.first]++;
}
}
else {
int c1, c2;
// c1 = y*dx - dy*dx
// If one of them is negative, then
// generalising that dx is negative and dy
// is positive so that we don't repeat
if (dx > 0 && dy < 0) {
dx *= -1, dy *= -1;
}
// Calculating the intercepts
c1 = Y[i] * dx - dy * X[i];
c2 = dx;
// Normalising the intercepts
int g2 = __gcd(c1, c2);
c1 /= g2, c2 /= g2;
pair<pair<int, int>, pair<int, int> > pr
= { { dx, dy }, { c1, c2 } };
if (st.find(pr) != st.end()) {
// Do nothing as this line is same just
// an etenstion to some line with same
// slope and intercept
}
else {
// Insert this line to the set
st.insert(pr);
// increase the count of the slope of
// this line
mp[pr.first]++;
}
}
}
}
// vector for storing all the counts
// of the lines with different parameters
vector<int> v;
for (auto count : mp) {
v.push_back(count.second);
}
// Counting all different line segments
int cnt = accumulate(v.begin(), v.end(), 0);
// Variable to store the count
int ans = 0;
for (int i = 0; i < v.size(); i++) {
// Decreasing the count by current line segments
// which will be parallel to each other
cnt -= v[i];
// Intersecting all other line
// segments with this line segment
ans += cnt * v[i];
}
return ans;
}
// Driver Code
int main()
{
// Given Input
int N = 4;
int X[] = { 0, 1, 0, 1 };
int Y[] = { 0, 1, 3, 2 };
// Function call
cout << totalPairsOfIntersectineLines(X, Y, N);
return 0;
}
Producción
14
Complejidad de tiempo: O(N*N*logN)
Complejidad espacial: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA