首页 > 编程语言 >[算法] A LITTLE 计算几何

[算法] A LITTLE 计算几何

时间:2024-09-24 21:01:26浏览次数:7  
标签:LITTLE int double 几何 凸包 算法 && poi include

叉积

有两个平面向量a, b,那么有 a $ \times $ b $ = x_a \times y_b - x_b \times y_a $;

这是有方向的,且遵守右手定则,正代表 a 逆时针转到 b,负代表顺时针;

凸包

求凸包,我用的 $ Graham $ 扫描法;

首先把最底下的点找出来,然后按照其它点对于这个点的角度排序,然后用一个类似于单调栈的东西维护一下即可;

时间复杂度: $ \Theta(n \log n) $

例题:Luogu P2742

点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
int n;
struct poi{
	double x, y;
	double operator ^(const poi &A) const {
		return x * A.y - y * A.x;
	}
}e[500005], s[500005];
int cnt;
double dis(poi x) {
	return sqrt(x.x * x.x + x.y * x.y);
}
bool cmp(poi x, poi y) {
	poi a = {x.x - e[1].x, x.y - e[1].y};
	poi b = {y.x - e[1].x, y.y - e[1].y};
	double c = a ^ b;
	if (c > 0.0) return 1;
	else if (c == 0.0 && dis(a) <= dis(b)) return 1;
	else return 0;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> e[i].x >> e[i].y;
		if (i != 1 && (e[1].y > e[i].y || (e[1].y == e[i].y && e[1].x > e[i].x))) swap(e[1], e[i]);
	}
	sort(e + 2, e + 1 + n, cmp);
	s[1] = e[1];
	cnt = 1;
	for (int i = 2; i <= n; i++) {
		poi a = {s[cnt].x - s[cnt - 1].x, s[cnt].y - s[cnt - 1].y};
		poi b = {e[i].x - s[cnt].x, e[i].y - s[cnt].y};
		while(cnt > 1 && ((a ^ b) <= 0.0)) {
			cnt--;
			a = {s[cnt].x - s[cnt - 1].x, s[cnt].y - s[cnt - 1].y};
			b = {e[i].x - s[cnt].x, e[i].y - s[cnt].y};
		}
		s[++cnt] = e[i];
	}
	s[++cnt] = e[1];
	double ans = 0.0;
	for (int i = 2; i <= cnt; i++) {
		ans += dis({s[i].x - s[i - 1].x, s[i].y - s[i - 1].y});
	}
	cout << fixed << setprecision(2) << ans;
	return 0;
}

旋转卡壳

以求凸包直径为例,我们的这个算法就是拿一组平行线去卡凸包,最后看哪个最大即可;

用双指针维护一下,每次找凸包的一条边,然后找最远的点即可;

时间复杂度:$ \Theta(n) $

标签:LITTLE,int,double,几何,凸包,算法,&&,poi,include
From: https://www.cnblogs.com/PeppaEvenPig/p/18428267

相关文章

  • 文心一言 VS 讯飞星火 VS chatgpt (354)-- 算法导论24.1 6题
    六、假定G=(V,E)为一带权重的有向图,并且图中存在一个权重为负值的环路。给出一个有效的算法来列出所有属于该环路上的结点。请证明算法的正确性。如果要写代码,请用go语言。文心一言:对于存在权重为负的环路的有向图,我们可以使用Bellman-Ford算法的一个变种来检测并列出该环路上的所......
  • Python实现图形学光照和着色的Gouraud着色算法
    目录使用Python实现图形学光照和着色的Gouraud着色算法引言1.Gouraud着色算法概述1.1算法原理2.Python实现Gouraud着色算法2.1向量类2.2光源类2.3材质类2.4Gouraud着色器类2.5使用示例3.实例分析4.Gouraud着色算法的优缺点4.1优点4.2缺点5.改进方向6.应......
  • Python实现Phong着色模型算法
    目录使用Python实现Phong着色模型算法引言Phong着色模型的基本原理1.模型组成2.公式Phong着色模型的Python实现1.向量类的实现2.光源类的实现3.材质类的实现4.Phong着色器类的实现整体实现总结使用Python实现Phong着色模型算法引言在计算机图形学中,光照和......
  • 美团2024年秋招第一场笔试【算法】
    1. 小美的因子查询题目链接:校招笔试真题_算法工程师、大数据开发工程师_牛客网小美对偶数因子很感兴趣,她将进行 T 次询问,每次都会给出一个正整数 x,请你告诉她 x 是否存在至少一个偶数因子。也就是说 x 是否存在某个因子是偶数。思路:一个数若存在因子是偶数则因子一......
  • 【代码随想录Day27】贪心算法Part01
    理论基础题目链接/文章讲解:代码随想录视频讲解:贪心算法理论基础!_哔哩哔哩_bilibili455.分发饼干题目链接/文章讲解:代码随想录视频讲解:贪心算法,你想先喂哪个小孩?|LeetCode:455.分发饼干_哔哩哔哩_bilibili一开始使用了双重循环,时间复杂度为......
  • 【代码随想录Day25】回溯算法Part04
    491.递增子序列题目链接/文章讲解:代码随想录视频讲解:回溯算法精讲,树层去重与树枝去重|LeetCode:491.递增子序列_哔哩哔哩_bilibiliclassSolution{List<List<Integer>>result=newArrayList<>();LinkedList<Integer>path=newLinkedList<>();pub......
  • Java:排序算法
    Java中有很多种排序算法,每种算法都有其特点,适用于不同的场景。下面列举一些常见的排序算法,并简要介绍其特点:冒泡排序(BubbleSort)原理:通过重复遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的,直到没有再需要交换的元素,这意......
  • 【深度学习】03-神经网络 3-3 梯度下降的优化方法-动量算法Momentum
    常规的梯度下降算法中,会遇到平缓区域,碰到鞍点,碰到局部最小值(截止当前无解),因此为了解决这个问题,我们需要优化传统的梯度下降算法。动量算法(Momentum)是梯度下降算法的一种优化方法,旨在解决传统梯度下降容易陷入局部最小值或在鞍点附近震荡的问题。动量算法通过引入一个“动......
  • 烟火识别算法、AI烟火识别算法、烟火检测算法
    烟火检测算法主要用于火灾早期预警系统中,能够在火灾初期阶段及时发现烟雾或火焰,从而快速响应并采取行动,以减少火灾带来的损失。这种技术广泛应用于公共安全、工业生产、家庭安全等领域。一、技术实现烟火检测算法通常依赖于计算机视觉和深度学习技术,通过分析图像或视频数据来检测......
  • 中秋献礼!2024年中科院一区极光优化算法+分解对比!VMD-PLO-Transformer-LSTM多变量时间
    中秋献礼!2024年中科院一区极光优化算法+分解对比!VMD-PLO-Transformer-LSTM多变量时间序列光伏功率预测目录中秋献礼!2024年中科院一区极光优化算法+分解对比!VMD-PLO-Transformer-LSTM多变量时间序列光伏功率预测效果一览基本介绍程序设计参考资料效果一览基本介绍1.中秋献礼!2024年......