归档: 2022/4 | Q779的博客

2022

04

29

[计算几何] 使用叉积计算直线交点

[计算几何] 使用叉积计算直线交点已知直线 $AB$ 和 $CD$ ，其交点为 $P$ ，求 $P$ 的坐标。计算几何中一般存储向量 $\vec{p},\vec{v}$ 表示起点的向量表示和方向向量例如直线

2022-04-29 OI

数学计算几何

28

半平面交的交集问题&POJ2451 Uyuw's Concert 题解

半平面交的交集问题&POJ2451 Uyuw's Concert 题解前言初学半平面交，就遇到了这样巨大的坑，也是挺无语... 判断交集为空的情况 poj2451 Uyuw's Concert Description Pri

2022-04-28 OI

算法数据结构计算几何

27

UVA12307 Smallest Enclosing Rectangle 题解

UVA12307 Smallest Enclosing Rectangle 题解 upd.20220429 由于q779太菜，导致代码出了点锅，已经重新修改题目链接：UVA12307 Smallest Enclosing Rectangl

2022-04-27 OI

算法数据结构计算几何

25

洛谷P4159 [SCOI2009] 迷路题解

洛谷P4159 [SCOI2009] 迷路题解题目链接：P4159 [SCOI2009] 迷路题意：该有向图有 $n$ 个节点，节点从 $1$ 至 $n$ 编号，windy 从节点 $1$ 出发，他必须恰好在 \(t

2022-04-25 OI

算法数学

25

洛谷P3829 [SHOI2012]信用卡凸包题解

洛谷P3829 [SHOI2012]信用卡凸包题解题目链接：P3829 [SHOI2012]信用卡凸包题意：给定若干个“信用卡”，求其“凸包”周长这个题其实看上去很不可做，其实很简单注意到（搬了一张图，来自link，不过

2022-04-25 OI

算法计算几何

23

洛谷P3194 [HNOI2008]水平可见直线题解

洛谷P3194 [HNOI2008]水平可见直线题解题目链接：P3194 [HNOI2008]水平可见直线题意：在$ x-y$ 直角坐标平面上有 $n$ 条直线 $L_1,L_2,…L_n$，若在 $y$ 值为正无穷大处

2022-04-23 OI

算法数据结构计算几何

22

洛谷P3236 [HNOI2014]画框题解

洛谷P3236 [HNOI2014]画框题解题目链接：P3236 [HNOI2014]画框题意：小 T 准备在家里摆放几幅画，为此他买来了 $N$ 幅画和 $N$ 个画框。为了体现他的品味，小 T 希望能合理地搭配画与画框，

2022-04-22 OI

算法图论数学数据结构计算几何

22

洛谷P5540 [BalkanOI2011] timeismoney | 最小乘积生成树题解

洛谷P5540 [BalkanOI2011] timeismoney | 最小乘积生成树题解题目链接：P5540 [BalkanOI2011] timeismoney | 最小乘积生成树题意：给出一个 $n$ 个点 $m$

2022-04-22 OI

算法数学计算几何

19

洛谷P2491 [SDOI2011] 消防题解

洛谷P2491 [SDOI2011] 消防题解题目链接：P2491 [SDOI2011] 消防题意：某个国家有 $n$ 个城市，这 $n$ 个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为 \(z_i\

2022-04-19 OI

算法图论数据结构

17

洛谷P3299 [SDOI2013]保护出题人题解

洛谷P3299 [SDOI2013]保护出题人题解题目链接：P3299 [SDOI2013]保护出题人题意：出题人铭铭认为给SDOI2012出题太可怕了，因为总要被骂，于是他又给SDOI2013出题了。参加SDOI2012的小朋友

2022-04-17 OI

算法计算几何