Spy97

计算几何

2018 Multi-University Training(7) 2019牛客多校(1) AC自动机(1) BFS(2) CCPC(7) Codeforces(16) DFS序(1) Hash(4) ICPC(6) pb_ds(2) 主席树(2) 分块(2) 分治(2) 动态规划(2) 博弈(4) 后缀数组(6) 回文树(2) 图论(15) 差分约束系统(1) 思维(8) 数学(2) 未归档(5) 树(5) 树链剖分(3) 模拟(1) 模拟退火(1) 矩阵快速幂(2) 线性基(1) 线段树(7) 莫队(1) 贪心(2)

/ 注册

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

牛客挑战赛33 C 艾伦的立体机动装置

题意给出一个多边柱体，从上底面的边缘的一点走到下底面边缘的一点，要求不能经过上底面，求最小距离题解首先，侧面展开是一个长方形，如果不能走下底面的话，就是一个长方形上两点的直线距离现在可以经过下底面那么，侧面和下底面的展开图会有很多可能，枚举下底面相连的底边，计算即可。侧面展开时，...

牛客挑战赛33 艾伦的立体机动装置

2019-10-24

0 368

Codeforces 1158D Winding polygonal line

题意给n个点，构造一个遍历顺序，共有 n-2 个转弯点，要求左转或右转的序列为题目要求的。题解看了官方的题解来的这个序列一定存在首先，出发点一定是一个角落里的点，不妨取最左下的点确定下一步要走的点的步骤将现在所在的点和未走的点连线如果是左转，则要取最考右的点，因为这样能保证...

Codeforces 1158D Winding polygonal line

2019-10-24

0 939

洛谷 P4557 LOJ P2549 [JSOI2018]战争闵可夫斯基和凸包

模板题代码 #include<bits/stdc++.h> #define N 200010 #define INF 0x3f3f3f3f #define eps 1e-5 #define pi 3.141592653589793 #define mod 998244353 // ...

2019-10-05

0 339

2019牛客暑期多校第八场 Flower Dance

题意给一些点，找4个点，要求1个点在剩余三个点围成的三角形的内部，问方案数题解写得我有种不想碰几何的冲动。。。。太迷了，精度迷，同一种意思的不同表达迷，明明那么简洁的思路，为什么写出来这么多特殊情况 😐 哭了枚举每一个点当做三角形内部的点，看有多少个三角形能包住他 1号能和（4...

2019-08-13

0 293

Codeforces 1146H Satanic Panic

题解首先，总的方案数为 C n 5 ...

2019-05-03

0 335

Codeforces 1142C U2 凸包

题解对于 ( x 1 , ...

2019-05-03

0 379

牛客练习赛29 C题枇杷

题意：二维平面的第一象限内，有两种操作，一是在某个点的权值加一，二是查询一个直角梯形范围内的权值的和。题解： std解法是CDQ分治，想了个分块暴力的方法，速度竟然是最快的。。。将整个第一象限分为128*128（1<<7）个块，每个块是边长为（1<<23）的正方...

2018-10-21

0 284

牛客国庆集训派对Day2 魔法阵

题意：给出3个点，确定一个正三角形，每个三角形的顶点一一对应一个给出的点，使对应的最大距离最小。题解：官方的给出最优解的样子代码： #include<bits/stdc++.h> #define N 1010 #define INF 0x3f3f3...

2018-10-02

0 317

2018 北京网络赛 G题 The Mole

题意：二维平面给出n条线段，每次提问一个点，输出到这个点距离最短的线段的编号。题解：数据随机，就暴力+RP了。。。坐标范围是2^16，将坐标每2^8一个分块，总共有2^16个块。读入一条线段时，将这条线段经过的所有块都加上当前线段的编号。读入一个询问，找到他属于第几块，然后枚举...

2018-09-22

0 321

2018 牛客多校第二场 C message

题意：给出n条直线，询问m次，每次询问给出一条直线，问这条直线与那n条直线的在y轴右侧交点的横坐标的最大值。题解：设交点为，则要使x最大，我将一条直线的两个系数a、b看做点（a，b），那么答案就是n个点中到询问点的斜率的最小值。为了方便和便于理解，我们将x坐标取反，转为求...

2018-09-19

0 348