首页
学习
活动
专区
工具
TVP
发布
您找到你想要的搜索结果了吗?
是的
没有找到

YbtOJ 824「计算几何初探」圆与连线

YbtOJ 824「计算几何初探」圆与连线 题目链接:YbtOJ #824 小 A 有一个平面直角坐标系,其中有一个圆心在原点的半径为 r 的圆(即它的方程为 x^2+y^2=r^2)和 n...小 A 想知道最多能够留下多少个特殊点,满足任意两点连线不与圆相交。 1\le n\le 2\times10^3,r,x_i,y_i\le5\times10^3。...Tutorial 求出每个点与圆的两条切线,那么在这两条切线之间的其他点与该点的连线都会与圆相交,而切线外的点则不会。...我们把每个点与圆的两个切点看成一个区间(具体实现中,方便起见我们我们用 角度 来表示这个区间),那么点 A 与其两条切线间的点 B,对应的区间必然包含(两点在圆的同侧)或是相离(两点在圆的异侧),也就是说两点连线无交当且仅当它们的区间是非包含关系的相交...求角度的区间还是比较简单的,首先我们求出当前点的角度 g,然后求出当前点与圆心的连线和圆心向切线的垂线的夹角 d(\cos d=\frac{\sqrt{x^2+y^2}}{R}),则 [g-d,g+d]

80720
领券