【Leetcode】469. Convex Polygon
admin
2024-01-21 06:20:34
0次

题目地址：

https://leetcode.com/problems/convex-polygon/description/

给定一个多边形的nnn个顶点坐标组成的数组AAA，题目保证按所给顺序遍历这些顶点可以得到一个nnn边形，问这个多边形是不是凸的。

看一下A[0]A[1]⃗×A[1]A[2]⃗\vec{A[0]A[1]}\times \vec{A[1]A[2]}A[0]A[1]​×A[1]A[2]​的符号（即指向纸面外还是内），然后依次计算A[k]A[k+1]⃗×A[k+1]A[k+2]⃗\vec{A[k]A[k+1]}\times \vec{A[k+1]A[k+2]}A[k]A[k+1]​×A[k+1]A[k+2]​的符号，如果其中一个符号与A[0]A[1]⃗×A[1]A[2]⃗\vec{A[0]A[1]}\times \vec{A[1]A[2]}A[0]A[1]​×A[1]A[2]​不同，则说明发生了凹陷，从而不是凸多边形。代码如下：

class Solution {public:bool isConvex(vector>& ps) {int n = ps.size();// 注意，最后还需要判断最后两个点和起始点的向量叉乘。ps.push_back(ps[0]);ps.push_back(ps[1]);int p = cross(ps[0], ps[1], ps[1], ps[2]) > 0 ? 1 : -1;for (int i = 0; i < n; i++)if (cross(ps[i], ps[i + 1], ps[i + 1], ps[i + 2]) * p < 0) return false;return true;}int cross(vector& a, vector& b, vector& c, vector& d) {int x1 = b[0] - a[0], x2 = d[0] - c[0];int y1 = b[1] - a[1], y2 = d[1] - c[1];return x1 * y2 - x2 * y1;}
};

时间复杂度O(n)O(n)O(n)，空间O(1)O(1)O(1)。

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：面试官：vue2和vue3的区别有哪些？

下一篇：字符串的转换路径问题

相关内容

热门资讯

下载灰灰影音安卓系统,畅享高清... 你有没有想过，一部手机，一部电脑，就能让你随时随地享受高清电影、热门剧集的乐趣？没错，这就是我们今天...
安卓系统是不是中国,中国智慧与... 你有没有想过，那个陪伴你每天刷手机、玩游戏、办公的安卓系统，它是不是中国的“孩子”呢？这个问题听起来...
电脑如果安装安卓系统,探索安卓... 你有没有想过，如果家里的电脑突然决定要换换口味，不再坚守Windows的阵营，而是拥抱安卓系统呢？想...
安卓手机升级苹果系统,体验全新... 你有没有想过，你的安卓手机突然间变成了苹果的忠实粉丝，想要体验一番iOS系统的魅力呢？这可不是天方夜...
安卓系统短信不通知,享受宁静 你是不是也遇到了这个问题？安卓系统短信不通知，是不是让你抓狂？别急，今天就来给你详细解析一下这个让人...
夏普电视非安卓系统,非安卓系统... 亲爱的读者们，你是否曾对夏普电视的非安卓系统感到好奇呢？今天，就让我带你一探究竟，揭开这个神秘面纱背...
安卓系统43适配软件,软件升级... 你有没有发现，你的安卓手机最近是不是有点儿“水土不服”？别急，别急，让我来给你揭秘为什么你的安卓系统...
安卓系统有车载系统吗吗,智能驾... 你有没有想过，当你坐在车里，享受着旅途的悠闲时光，手机上的安卓系统是不是也能派上用场呢？没错，我就要...
安卓8.1系统解锁方法,畅享自... 你有没有想过，你的安卓手机里隐藏着无数的小秘密？比如，解锁安卓8.1系统，就能让你的手机焕发出全新的...
安卓系统怎么打开邮件,安卓系统... 你有没有想过，每天那么多邮件，怎么才能快速打开它们呢？尤其是当你用的是安卓系统手机的时候。别急，今天...
封闭安卓系统安装软件,一步到位... 你有没有想过，为什么你的安卓手机里有些软件只能通过官方渠道安装呢？今天，就让我带你一探究竟，揭开封闭...
小米mipad升级安卓系统,解... 你有没有发现，最近小米Mipad的安卓系统升级可是个大热门呢！这不，我就迫不及待地来和你聊聊这个话题...
哪个安卓系统体验好,揭秘安卓系... 你有没有想过，手机里的安卓系统就像是个大厨，不同的版本就是不同的拿手好菜，有的让你回味无穷，有的却让...
安卓系统开发测试,全方位技术解... 你有没有想过，那个陪伴你每天刷手机、玩游戏、办公的安卓系统，是怎么从无到有，一步步成长起来的呢？今天...
安卓系统怎么查配置,轻松掌握设... 你有没有想过，你的安卓手机里藏着多少秘密？别小看这些配置信息，它们可是了解你手机性能的“小侦探”呢！...
pve下安装安卓系统,PVE环... 你有没有想过，在你的PVE服务器上安装一个安卓系统呢？听起来是不是有点酷炫？想象你的服务器不仅能够运...
安卓手机安装虹膜系统,安卓手机... 你有没有想过，你的安卓手机还能这样玩？没错，就是安装虹膜系统！听起来是不是有点酷炫？别急，让我带你一...
小米论坛原生安卓系统,深度解析... 你有没有想过，你的手机系统其实可以更加纯粹、更加原生？今天，就让我带你走进小米论坛，一探究竟，看看那...
安卓怎么装iphone系统,轻... 你是不是也和我一样，对安卓手机上的iPhone系统充满了好奇？想象那流畅的界面、强大的性能，还有那独...
模拟器系统安卓,打造移动应用开... 你有没有想过，在手机上也能体验到电脑游戏的快感？没错，这就是安卓模拟器系统的魅力所在！今天，就让我带...