计算几何目录下的文章
[BZOJ 1336] 最小圆覆盖
题目描述
给出N个点,画一个最小的包含所有点的圆。
输入格式
先给出点的个数N \; (2 \le N \le 100000),再给出坐标x_i,y_i \; (-10000.0 \le x_i,y_i \le 10000.0)
输出格式
输出圆的半径,及圆心的坐标。
题目解析
最小覆盖圆问题是计算几何中的经典问题,对于本题有一种神奇……
[BZOJ 1007] 水平可见直线
题目描述
在XoY直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为可见的,否则Li为被覆盖的。例如,对于直线:L1:y=x; L2:y=-x; L3:y=0,则L1和L2是可见的,L3是被覆盖的。
给出n条直线,表示成y=Ax+B的形式(|A|,|B|<=500000),且n条直……