首页 > 编程语言 >c++ 找到给定点集的简单闭合路径(Find Simple Closed Path for a given set of points)

c++ 找到给定点集的简单闭合路径(Find Simple Closed Path for a given set of points)

时间:2024-09-18 13:53:28浏览次数:10  
标签:p2 given set Point int p1 c++ points point

给定一组点,将这些点连接起来而不相交

例子: 

输入:points[] = {(0, 3), (1, 1), (2, 2), (4, 4),
                   (0, 0), (1, 2), (3, 1}, {3, 3}};

输出:按以下顺序连接点将
        不造成任何交叉
       {(0, 0), (3, 1), (1, 1), (2, 2), (3, 3),
        (4,4),(1,2),(0,3)}
        
我们强烈建议您最小化浏览器并先自己尝试一下。

这个想法是使用排序。 

通过比较所有点的 y 坐标来找到最底部的点。如果有两个点的 y 值相同,则考虑 x 坐标值较小的点。将最底部的点放在第一个位置。 

考虑剩余的 n-1 个点,并围绕 points[0] 按照极角逆时针顺序排列它们。如果两个点的极角相同,则将最近的点放在最前面。

遍历排序数组(按角度升序排序)产生简单的闭合路径。

如何计算角度? 
一种解决方案是使用三角函数。 
观察:我们不关心角度的实际值。我们只想按角度排序。 
想法:使用方向来比较角度,而无需实际计算它们!

以下是上述想法的实现:

// A C++ program to find simple closed path for n points
// for explanation of orientation()
#include <bits/stdc++.h>
using namespace std;
 
struct Point
{
    int x, y;
};
 
// A global point needed for  sorting points with reference
// to the first point. Used in compare function of qsort()
Point p0;
 
// A utility function to swap two points
int swap(Point &p1, Point &p2)
{
    Point temp = p1;
    p1 = p2;
    p2 = temp;
}
 
// A utility function to return square of distance between
// p1 and p2
int dist(Point p1, Point p2)
{
    return (p1.x - p2.x)*(p1.x - p2.x) +
           (p1.y - p2.y)*(p1.y - p2.y);
}
 
// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are collinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);
 
    if (val == 0) return 0;  // collinear
    return (val > 0)? 1: 2; // clockwise or counterclock wise
}
 
// A function used by library function qsort() to sort
//  an array of points with respect to the first point
int compare(const void *vp1, const void *vp2)
{
   Point *p1 = (Point *)vp1;
   Point *p2 = (Point *)vp2;
 
   // Find orientation
   int o = orientation(p0, *p1, *p2);
   if (o == 0)
     return (dist(p0, *p2) >= dist(p0, *p1))? -1 : 1;
 
   return (o == 2)? -1: 1;
}
 
// Prints simple closed path for a set of n points.
void printClosedPath(Point points[], int n)
{
   // Find the bottommost point
   int ymin = points[0].y, min = 0;
   for (int i = 1; i < n; i++)
   {
     int y = points[i].y;
 
     // Pick the bottom-most. In case of tie, choose the
     // left most point
     if ((y < ymin) || (ymin == y &&
         points[i].x < points[min].x))
        ymin = points[i].y, min = i;
   }
 
   // Place the bottom-most point at first position
   swap(points[0], points[min]);
 
   // Sort n-1 points with respect to the first point.
   // A point p1 comes before p2 in sorted output if p2
   // has larger polar angle (in counterclockwise
   // direction) than p1
   p0 = points[0];
   qsort(&points[1], n-1, sizeof(Point), compare);
 
   // Now stack has the output points, print contents
   // of stack
   for (int i=0; i<n; i++)
       cout << "(" << points[i].x << ", "
            << points[i].y <<"), ";
}
 
// Driver program to test above functions
int main()
{
    Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},
                       {0, 0}, {1, 2}, {3, 1}, {3, 3}};
    int n = sizeof(points)/sizeof(points[0]);
    printClosedPath(points, n);
    return 0;
}

输出: 

(0, 0), (3, 1), (1, 1), (2, 2), (3, 3),
(4,4),(1,2),(0,3),
如果我们使用 O(nLogn) 排序算法对点进行排序,则上述解决方案的时间复杂度为 O(n Log n)。
辅助空间: O(1),因为没有占用额外空间。

来源: 
http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf

标签:p2,given,set,Point,int,p1,c++,points,point
From: https://blog.csdn.net/hefeng_aspnet/article/details/141715783

相关文章

  • C# 找到给定点集的简单闭合路径(Find Simple Closed Path for a given set of points)
     给定一组点,将这些点连接起来而不相交例子: 输入:points[]={(0,3),(1,1),(2,2),(4,4),          (0,0),(1,2),(3,1},{3,3}};输出:按以下顺序连接点将    不造成任何交叉    {(0,0),(3,1),(1,1),(2,2),(3,3)......
  • zblogphp错误之“未知方法或属性 (set_error_handler)
    当你在Z-BlogPHP中遇到“未知方法或属性(set_error_handler)”的错误时,这通常意味着PHP版本不支持 set_error_handler 函数。该函数在PHP5.0及更高版本中可用。如果你的PHP版本低于5.0,你可能会遇到这个问题。解决方案检查PHP版本确认当前PHP版本是否支持......
  • Zblog unserialize(): Error at offset 2 of 686 bytes
    当在Z-Blog中遇到 unserialize():Erroratoffset2of686bytes 这个错误时,通常表示在反序列化操作中出现了问题。这种错误可能是由多种原因导致的。以下是排查和解决这个问题的一些步骤:1.检查数据源问题描述:反序列化的数据源可能有问题。解决方法:检查数据源(通常是......
  • C++信奥老师解一本通题 1164:digit函数
    ​【题目描述】在程序中定义一函数digit(n,k),它能分离出整数n从右边数第k个数字。【输入】正整数n和k。【输出】一个数字。【输入样例】318593【输出样例】8#include<iostream>usingnamespacestd;intdigit(longlongn,intk){ if(k==1) returnn%10......
  • C++信奥老师解一本通题 1369:合并果子(fruit)
    ​【题目描述】在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n−1次合并之后,就只剩下一堆了。多多在合并......
  • C++学习笔记(26)
    七、显示字符串中的字符从界面上输入一个字符串(C风格),把字符串中的每个字符显示出来,如果输入的是"abc",要求:1)正序显示:abc2)逆序显示:cba求字符串的长度可以利用上一题的成果,也可以直接用strlen()函数,关注性能的细节。示例:#include<iostream>usingnamespacestd;//......
  • C++实现的小游戏
    大家好,这几天做项目太忙,时间不够去更新,十分抱歉。今天凌晨花了半个点的时间写了一个小游戏的青春版,给大家分享。游戏名:想玩电脑?先过我这关!首先我先来说明一下游戏的规则:我们用C++写了一个0~100的随机数,用户有五次机会可以猜数字,猜对了就可以玩电脑,猜错了电脑就会关机(当然你要......
  • 最优化理论与自动驾驶(十一):基于iLQR的自动驾驶轨迹跟踪算法(c++和python版本)
    最优化理论与自动驾驶(四):iLQR原理、公式及代码演示之前的章节我们介绍过,iLQR(迭代线性二次调节器)是一种用于求解非线性系统最优控制最优控制最优控制和规划问题的算法。本章节介绍采用iLQR算法对设定的自动驾驶轨迹进行跟踪,与第十章节纯跟踪算法采用同样跟踪轨迹,同时,我们仅对控......
  • C++_指针的超详细讲解,带你层层深入理解指针
    C++ 指针学习C++的指针既简单又有趣。通过指针,可以简化一些C++编程任务的执行,还有一些任务,如动态内存分配,没有指针是无法执行的。所以,想要成为一名优秀的C++程序员,学习指针是很有必要的。正如您所知道的,每一个变量都有一个内存位置,每一个内存位置都定义了可使用连字号......
  • 【C/C++】涉及string类的经典OJ编程题
    【C/C++】涉及string类的经典OJ编程题一.把字符串转化成整数(atoi)解法一:(不用long)完整代码:解法二:(用long)二.字符串相加代码实现(含注释):三.反转字符串代码实现:四.字符串中的第一个唯一字符解法一:解法二:(推荐)一.把字符串转化成整数(atoi)点这里:本题LeetCode链接该题源......