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篇）

codeforces 886F 889D 890F Symmetric Projections

这题我写吐了，交了31发，最后一发AC，尝试了各种写法以及各种假优化，最后从别人的代码片段中获得灵感，感慨还是自己太蠢了。。。题意： n个点，有一条过原点的直线，如果所有点在这条直线上的投影点是关于某个点对称的，那么这条直线就是GOOD，问这样直线的个数。题解：首先要求出所有点的...

codeforces 886F 889D 890F

2018-09-14

0 451

2018 ICPC 沈阳网络赛 The cake is a lie

题意：给出n个半径一致的圆，画一个圆至少完全包含其中的m个，求最小半径。题解：可化简为，n个点，求覆盖掉至少m个的最小的圆 O(n^2logn *logR）的解法：二分半径，然后判断这个半径下能覆盖的最多的点，若小于要求，半径变大，若大于要求，半径缩小。如何得知一个半径下能覆盖...

2018-09-11

0 417

codeforces 1019D Large Triangle

题意：给出n个点和一个面积s，问能否从n个点中选3个点组成s的三角形的面积为s。题解: 这题我思考了很久，因为确实方法不是很好懂。首先，原题是bzoj 3707，这道题是给出n个点，求3个点组成的最小面积。我们先从这题入手。解法一：分块+暴力将坐标系多...

2018-08-27

0 545

codeforces 1025F Disjoint Triangles

题意：给出n个点，保证没有三点共线，求可以组成多少对不相交的三角形。题解：对于两个不相交的三角形A、B，我们发现有且仅有两条共切线能使得直线两侧是完整的三角形。我的思路就是枚举直线，直线上已经有2个点了，假设直线两侧分别有x、y个点，那么可行的方案就是一侧选两个点，和直线上的点构成三...

2018-08-24

0 486

HDU 6419 Rikka with Rain （暴力）

题意：有一个多边形，提问m个圆，求圆被多边形完全包含需要移动的最少距离。题解：做过的一道目前最难的几何题，充分发挥了暴力的思想。看到这个问题的第一想法就是，多边形向内缩R（圆的半径），然后求圆心到缩小的多边形的最短距离即可。方法就是枚举新的多边形的线段，求点到线段的最短距离。那么...

2018-08-23

0 418

HDU 6398

题意：给一个三角形，放在一个给定宽度的无线长的矩形中，要求占得长度最小。题解：分两种情况，一是三角形的边与矩形的边重合，二是三角形的两个点卡在矩形的两条边上。对于第一种情况，枚举底边，算出第三点在底边的投影，就知道要占据的最小宽度，若小于等于矩形宽度，再算出占据的高度。对于第二种...

2018-08-18

0 502

codeforces 958E3

题意：给出n个A类点和n个B类点，AB配对，要求连线不能有交点，输出方案。题解：感觉是个匹配，想不到解法，学习了别人的代码，原来是分治，长知识了。。。分治的思想是确定一个配对后，然后去解决确定配对的左边和右边。那么如何保证两边一定有解呢？方法比较巧妙。假设当前处理的区间为，我...

2018-08-11

0 365

扫描线

一、矩阵面积并（HDU 1542） #include<bits/stdc++.h> #define N 2010 using namespace std; struct seg { int l,r,h,d; seg(){} seg(int l,int r,...

2018-08-09

0 336

2018上海大都会赛 C题 Rescue

补完题后忙着补其他的了，就光把代码贴出来了，突然发现有人看，赶忙把题解发出来。题意：求两条线段的最近距离。题解：首先求空间中两条异面直线的距离为d，求的方法是板子。。。然后分两种情况：一是，首先我们定义两条直线的距离的方向为v，也就是说，一条直线沿方向v平移，会与另一条直线相交。...

2018-08-05

0 419

codeforces 698D

题意：给出m个射击位置，和n个静止的射击目标，在每个射击位置只能开一枪，问有多少位置是可能被射击到的。题解：对每个目标单独独立判断是否可能被射击到即可，判断方法是dfs，关键是dfs的方法。找到合适高效的dfs是关键，我就在这里跪倒了，太菜了，最后学习了codeforces里大佬的...

2018-07-30

0 508