icpc训练 SDNU ACM-ICPC 2020 Extra Training Contest 30：Begin: 2020-10-15 18:30 CSTEnd: 2020-10-15 21:50 CST比赛链接：https://vjudge.net/contest/401586比赛密码：202 ...

题目链接戳此处🗡数据下载┏┛墓┗┓…(((m -__-)m)) 解析注意，此处码头指的是一条直线。。 a straight line passing throughtwo distinct points with coordinates (0, 0)(0,0) and (A, B)(A,B). ...

题目大意题目很长，是有关于WOW的一个攻略出的模拟题。大致意思就是给你一堆点和一堆圆，问你在符合题意下，最多能连几条线段。要求如下： 线段不能相交，端点重合除外 线段不能与圆相交或相切 线段两个端点不能相邻，如$(i,i+1)$ 或$(i-1,i)$ 端点必须最靠外 根据这四条要求,就可以做了 ...

大意为了阻止战争,你就是,天选之人~~ 解析假设$a\in A,b\in B$,存在向量$w$,使得$b+w=a$,那么根据闵可夫斯基差,可以得到$A-B=\{w\rvert w+B\subseteq A\}$当然,解题都是怎么方便怎么来,我们直接将$B$取反,然后和$A$求个闵可夫斯基和就完事了. ...

定义什么是闵可夫斯基和?两个凸包$A$,$B$,那么他们的和$A+B=C$,其中,对于$C$中的每个坐标,都有$(x_C,y_C)=(x_A+x_B,y_A+y_B)$.定义为:$A+B=\{a+b\rvert a\in A,b\in B\}$最暴力的解法,便是对$A$中每一个点,都加一遍$B$中的 ...

题目大意在一个凸包里,找一个点$p$,使得该点与$\{k,k+1,k\in(1,n-1)\}$组成的三角形面积大于和$\{0,1\}$组成的三角形面积. 解析首先,我们考虑点的取值范围.必定在凸包内以及凸包的边界上.用线性规划半平面交表示即为:每个边所在直线的左半边区域交集.再考虑,三角形面积关系: ...

首先是定义 一条直线和直线的一侧称为一个半平面。半平面是一个点集，因此是一条直线和直线的一侧构成的点集。当包含直线时，称为闭半平面；当不包含直线时，称为开半平面。 一般来讲,都写成$ax+by+c\ge 0$.是不是很眼熟,线性规划记得不,还有各种鬼畜应用题.用来求$ ...

前置知识:最小圆覆盖洛谷P1742 最小圆覆盖  给定平面一定数量的点,找一个最小的圆,将所有点包含进去.  然后,就不记得是哪位大佬提出了一种$O(n)$的解决方式,随机增量法. 保证数据的随机性,我们使用$random\_shuffle$这个函数 我们要 ...

题目大意膜拜一位霓虹大佬%%%% 平面上有一堆不重叠的硬币.给定硬币的起点和终点,问最多可以把多少个硬币从起点直线移动到终点,且不会与其他硬币碰撞. 解析状压$dp$+计算几何一个硬币能否移动的条件为:第$i$枚硬币的起点和终点的连线L,与第$j$个硬币中心的距离$d$是否大于这俩个硬币半径的和.即 ...

2018-2019 ACM-ICPC, China Multi-Provincial Collegiate Programming ContestThe 2018/2019 Asia Yinchuan First Round Online Programming题目大意一个凸包,凸包上有一个点$G$ ...