归档: 2022/4 | Q779的博客

2022

04

29

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

[计算几何] 使用叉积计算直线交点 upd.本文写于远古时期，有空再来修改。已知直线 $AB$ 和 $CD$ ，其交点为 $P$ ，求 $P$ 的坐标。计算几何中一般存储向量 $\mathbf{p},\mathbf{v}$ 表示起点

2022-04-29 OI

数学咕咕计算几何

28

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

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

2022-04-28 OI

算法数据结构计算几何

27

UVA12307 Smallest Enclosing Rectangle 题解

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

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

算法计算几何