Dados n puntos 2-D points [] , la tarea es encontrar el perímetro del casco convexo para el conjunto de puntos. Un casco convexo para un conjunto de puntos es el polígono convexo más pequeño que contiene todos los puntos. Ejemplos:
Entrada: puntos[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}} Salida : 12 Entrada: puntos[] = {{0, 2}, {2, 1}, {3, 1}, {3, 7}} Salida: 15.067
Enfoque: el algoritmo de string monótona construye el casco convexo en tiempo O (n * log (n)) . Primero tenemos que clasificar los puntos y luego calcular los cascos superior e inferior en tiempo O(n) . Los puntos se ordenarán con respecto a las coordenadas x (con respecto a las coordenadas y en caso de empate en las coordenadas x), luego buscaremos el punto más a la izquierda y luego intentaremos girar en el sentido de las agujas del reloj y encontrar el siguiente punto y luego repita el paso hasta llegar al punto más a la derecha y luego gire nuevamente en el sentido de las agujas del reloj y encuentre el casco inferior. Luego encontraremos el perímetro del casco convexo usando los puntos en el casco convexo que se puede hacer en O (n)tiempo ya que los puntos ya están ordenados en el sentido de las agujas del reloj. A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the approach
#include <bits/stdc++.h>
#define llu long long int
using namespace std;
struct Point {
llu x, y;
bool operator<(Point p)
{
return x < p.x || (x == p.x && y < p.y);
}
};
// Cross product of two vectors OA and OB
// returns positive for counter clockwise
// turn and negative for clockwise turn
llu cross_product(Point O, Point A, Point B)
{
return (A.x - O.x) * (B.y - O.y)
- (A.y - O.y) * (B.x - O.x);
}
// Returns a list of points on the convex hull
// in counter-clockwise order
vector<Point> convex_hull(vector<Point> A)
{
int n = A.size(), k = 0;
if (n <= 3)
return A;
vector<Point> ans(2 * n);
// Sort points lexicographically
sort(A.begin(), A.end());
// Build lower hull
for (int i = 0; i < n; ++i) {
// If the point at K-1 position is not a part
// of hull as vector from ans[k-2] to ans[k-1]
// and ans[k-2] to A[i] has a clockwise turn
while (k >= 2
&& cross_product(ans[k - 2],
ans[k - 1], A[i]) <= 0)
k--;
ans[k++] = A[i];
}
// Build upper hull
for (size_t i = n - 1, t = k + 1; i > 0; --i) {
// If the point at K-1 position is not a part
// of hull as vector from ans[k-2] to ans[k-1]
// and ans[k-2] to A[i] has a clockwise turn
while (k >= t
&& cross_product(ans[k - 2],
ans[k - 1], A[i - 1]) <= 0)
k--;
ans[k++] = A[i - 1];
}
// Resize the array to desired size
ans.resize(k - 1);
return ans;
}
// Function to return the distance between two points
double dist(Point a, Point b)
{
return sqrt((a.x - b.x) * (a.x - b.x)
+ (a.y - b.y) * (a.y - b.y));
}
// Function to return the perimeter of the convex hull
double perimeter(vector<Point> ans)
{
double perimeter = 0.0;
// Find the distance between adjacent points
for (int i = 0; i < ans.size() - 1; i++) {
perimeter += dist(ans[i], ans[i + 1]);
}
// Add the distance between first and last point
perimeter += dist(ans[0], ans[ans.size() - 1]);
return perimeter;
}
// Driver code
int main()
{
vector<Point> points;
// Add points
points.push_back({ 0, 3 });
points.push_back({ 2, 2 });
points.push_back({ 1, 1 });
points.push_back({ 2, 1 });
points.push_back({ 3, 0 });
points.push_back({ 0, 0 });
points.push_back({ 3, 3 });
// Find the convex hull
vector<Point> ans = convex_hull(points);
// Find the perimeter of convex polygon
cout << perimeter(ans);
return 0;
}
12
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA