Requisitos previos: BIT
Dados ‘n’ segmentos de línea, cada uno de ellos es horizontal o vertical, encuentre el número máximo de triángulos (incluidos los triángulos con área cero) que se pueden formar uniendo los puntos de intersección de los segmentos de línea.
No se superponen dos segmentos de línea horizontal, ni tampoco dos segmentos de línea vertical. Una línea se representa usando dos puntos (cuatro números enteros, los dos primeros son las coordenadas x e y, respectivamente para el primer punto y los otros dos son las coordenadas x e y para el segundo punto)
Ejemplos:
|
---|-------|--
| | -----
| --|--|- |
| | |
For the above line segments, there are four points of intersection between
vertical and horizontal lines, every three out of which form a triangle,
so there can be 4C3 triangles.
La idea se basa en el algoritmo Sweep Line .
Construyendo una solución en pasos:
- Almacene ambos puntos de todos los segmentos de línea con el evento correspondiente (descrito a continuación) en un vector y clasifique todos los puntos, en orden no decreciente de sus coordenadas x.
- Ahora imaginemos una línea vertical que barramos a través de todos estos puntos y describamos 3 eventos, según el punto en el que nos encontramos actualmente:
- in – punto más a la izquierda de un segmento de línea horizontal
- out – punto más a la derecha de un segmento de línea horizontal
- una linea vertical
- Llamamos “activa” a la región o “activa” a las líneas horizontales que han tenido el primer evento pero no el segundo. Tendremos un BIT (árbol indexado binario) para almacenar las coordenadas ‘y’ de todas las líneas activas.
- Una vez que una línea se vuelve inactiva, eliminamos su ‘y’ del BIT.
- Cuando ocurre un evento de tercer tipo, es decir, cuando estamos en una línea vertical, consultamos el árbol en el rango de sus coordenadas ‘y’ y sumamos el resultado al número de puntos de intersección hasta el momento.
- Finalmente, tendremos el número de puntos de intersección, digamos m , luego el número de triángulos (incluyendo el área cero) será m C 3 .
Nota: Necesitamos ordenar cuidadosamente los puntos, mirar la función cmp() en la implementación para aclarar.
// A C++ implementation of the above idea
#include<bits/stdc++.h>
#define maxy 1000005
#define maxn 10005
using namespace std;
// structure to store point
struct point
{
int x, y;
point(int a, int b)
{
x = a, y = b;
}
};
// Note: Global arrays are initially zero
// array to store BIT and vector to store
// the points and their corresponding event number,
// in the second field of the pair
int bit[maxy];
vector<pair<point, int> > events;
// compare function to sort in order of non-decreasing
// x coordinate and if x coordinates are same then
// order on the basis of events on the points
bool cmp(pair<point, int> &a, pair<point, int> &b)
{
if ( a.first.x != b.first.x )
return a.first.x < b.first.x;
//if the x coordinates are same
else
{
// both points are of the same vertical line
if (a.second == 3 && b.second == 3)
{
return true;
}
// if an 'in' event occurs before 'vertical'
// line event for the same x coordinate
else if (a.second == 1 && b.second == 3)
{
return true;
}
// if a 'vertical' line comes before an 'in'
// event for the same x coordinate, swap them
else if (a.second == 3 && b.second == 1)
{
return false;
}
// if an 'out' event occurs before a 'vertical'
// line event for the same x coordinate, swap.
else if (a.second == 2 && b.second == 3)
{
return false;
}
//in all other situations
return true;
}
}
// update(y, 1) inserts a horizontal line at y coordinate
// in an active region, while update(y, -1) removes it
void update(int idx, int val)
{
while (idx < maxn)
{
bit[idx] += val;
idx += idx & (-idx);
}
}
// returns the number of lines in active region whose y
// coordinate is between 1 and idx
int query(int idx)
{
int res = 0;
while (idx > 0)
{
res += bit[idx];
idx -= idx & (-idx);
}
return res;
}
// inserts a line segment
void insertLine(point a, point b)
{
// if it is a horizontal line
if (a.y == b.y)
{
int beg = min(a.x, b.x);
int end = max(a.x, b.x);
// the second field in the pair is the event number
events.push_back(make_pair(point(beg, a.y), 1));
events.push_back(make_pair(point(end, a.y), 2));
}
//if it is a vertical line
else
{
int up = max(b.y, a.y);
int low = min(b.y, a.y);
//the second field of the pair is the event number
events.push_back(make_pair(point(a.x, up), 3));
events.push_back(make_pair(point(a.x, low), 3));
}
}
// returns the number of intersection points between all
// the lines, vertical and horizontal, to be run after the
// points have been sorted using the cmp() function
int findIntersectionPoints()
{
int intersection_pts = 0;
for (int i = 0 ; i < events.size() ; i++)
{
//if the current point is on an 'in' event
if (events[i].second == 1)
{
//insert the 'y' coordinate in the active region
update(events[i].first.y, 1);
}
// if current point is on an 'out' event
else if (events[i].second == 2)
{
// remove the 'y' coordinate from the active region
update(events[i].first.y, -1);
}
// if the current point is on a 'vertical' line
else
{
// find the range to be queried
int low = events[i++].first.y;
int up = events[i].first.y;
intersection_pts += query(up) - query(low);
}
}
return intersection_pts;
}
// returns (intersection_pts)C3
int findNumberOfTriangles()
{
int pts = findIntersectionPoints();
if ( pts >= 3 )
return ( pts * (pts - 1) * (pts - 2) ) / 6;
else
return 0;
}
// driver code
int main()
{
insertLine(point(2, 1), point(2, 9));
insertLine(point(1, 7), point(6, 7));
insertLine(point(5, 2), point(5, 8));
insertLine(point(3, 4), point(6, 4));
insertLine(point(4, 3), point(4, 5));
insertLine(point(7, 6), point(9, 6));
insertLine(point(8, 2), point(8, 5));
// sort the points based on x coordinate
// and event they are on
sort(events.begin(), events.end(), cmp);
cout << "Number of triangles are: " <<
findNumberOfTriangles() << "\n";
return 0;
}
Producción:
Number of triangles are: 4
Time Complexity: O( n * log(n) + n * log(maximum_y) )
Este artículo es una contribución de Saumye Malhotra . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA