何事秋。

计算几何

AC自动机(4) bfs/dfs(5) bitset(3) CF刷题(23) dp一般看规律(11) dp基本算法(12) KMP(2) LCA(1) LCT(4) Prufer(2) SAM(3) STL(1) tarjan(1) 主席树/线段树(14) 二分/三分(2) 二分图(1) 位运算(1) 偏序问题(2) 分块(1) 分治/点分治/边分治(2) 单调栈(2) 单调队列(1) 博弈/sg(3) 博弈论基本算法(11) 后缀数组(1) 启发式合并(1) 哈希(4) 回文自动机(2) 图论一顿套模板(3) 图论基本算法(31) 基本算法(2) 多项式(1) 套题(1) 字典树(1) 字符串基本算法(27) 容斥(1) 平衡树/堆(2) 并查集(3) 序列自动机(1) 快速幂/矩阵快速幂(1) 思维只会A+B(5) 投稿(2) 拓扑序(1) 数位dp(1) 数学不好先打表(4) 数据结构基本算法(69) 数据结构瞎乱写(8) 数论分块(1) 数论只会gcd(20) 数论基本算法(64) 暴力(1) 最短路(3) 期望/概率(1) 期望dp/概率dp(1) 构造(3) 枚举(3) 树形dp(3) 树链剖分(5) 模拟只会猜题意(5) 生成树(1) 签到题(2) 线性dp(12) 线性基(2) 组合数学(1) 组合数学靠运气(2) 结论题(2) 网络流/费用流(5) 网络流基本算法(5) 群论(2) 背包dp(1) 莫比乌斯反演(1) 莫队(1) 虚树(1) 计数类dp(1) 计算几何基本算法(15) 贪心刚好过样例(3) 随机化算法(2)

/ 注册

全部文章 / 计算几何（共8篇）

P3194 [HNOI2008]水平可见直线（直线交）

题目链接题面：题解：我们先按照直线的斜率从小到大排序，斜率相同按照b从大到小排序。现在考虑按照斜率排好序的三条直线 i - 1 ，i ，i +1 若 i 与 i + 1 的交点在 i 与 i - 1 交点的左侧，那么 i 不可见。代码： #include<iostream&...

2020-09-04

0 579

2020牛客暑期多校训练营（第二场） B、Boundary （暴力枚举）

题目链接题面：题意：给定n个点，对于一个过原点的圆，求出最多能经过多少个点。官方题解：我的题解：两维枚举 i，j ，对于一个固定的 i 来说，看看后面有多少个点是共圆的。不在一条直线上的三点可以确定一个圆。 ( 0 , 0 )，p [ i ] , p [ j ] 即可确定一...

2020-09-04

0 494

2020牛客暑期多校训练营（第二场） K、Keyboard Free （计算几何，期望）

题目链接题面：题意：给定三个同心圆，在这三个圆上分别选择一点，然后问这三点组成的三角形的面积的期望值。官方题解：题解：就是说A点任意确定即可，然后我们可以等分一个半圆枚举B点，求出C点到AB距离的期望。一开始是写出AB的表达式，然后再用距离公式求出期望，发现。。。积分积不动...

2020-09-04

0 364

2020牛客暑期多校训练营（第四场）F、Finding the Order （计算几何）

题目链接题面：题意：给定ac,ad,bc,bd 的长度，问是AB//CD ，还是AB//DC 题解：根据梯形对角线长度和一定大于两腰长度和。 #include<iostream> #include<cstdio> #include<cstdlib>...

2020-09-04

0 441

2020 Multi-University Training Contest 1---- HDU--6759、Leading Robots （可见直线、直线交）

题目链接题面：题意：在一个水平数轴上有n个点，给定每个点的坐标和加速度，每个点的初始速度均为0，这些点同时开始向右运动，可向右延伸至无穷远。问有多少个点在某一时刻成为过最右边的点，若最右边的点是两点并列，那么他们都不算最右边的点。题解：我们写出每个点的位移–时间表达式，其中位移...

2020-09-04

0 474

2020 Multi-University Training Contest 1---- HDU--6762、Mow（半平面交、思维）

题目链接题面：题意：给定一个凸多边形的草坪来割草，有两种方式：人工割草，单位代价为A，可以随意在任何位置割草半径为 r 的圆形割草机割草，单位代价为B，要求是割草机不能超过草坪的边界求割草的最小花费。题目保证 r 不等于给定凸包的内切圆半径。题解：如果人工割草更优，直接...

2020-09-04

0 529

2020牛客暑期多校训练营（第三场）C、Operation Love（计算几何，叉积）

题目链接题面：题意：题图给定的是右手，左手与右手完全对称。每只手由20个点组成。输入每次按照顺时针或者逆时针给定20个点，判断这些点组成的左右还是右手，其中给定的点是由题图的点旋转或者平移后保留6位小数得到，不会放大或者缩小。题解：选择（1，0），（1，6），（10，0）三个点...

2020-09-04

0 589

2020 Multi-University Training Contest 3---- HDU--6798、Triangle Collision（计算几何）

题目链接题面：题意：给一个等边三角形，初始时刻有一个点在其中，位置和速度矢量已知，这个球和三角形的边界发生完全弹性碰撞，且不记摩擦，求第k次碰撞发生的时间。k≤106 官方题解：我们把空间看为一张这样的无限大的平面。问题就变成了求小球做直线匀速运动，且与途中的边第k次相交是...

2020-09-04

0 457