题目链接 题意： 给定二维平面的n个点，要求一个面积最小的正方形，使其能覆盖所有的点。 思路： 先考虑如果水平竖直地放置正方形（边和坐标轴平行）圈住所有点的最小正方形的边长是: L=max(xmax−xmin,ymax−ymin) 然后考虑如果正方形旋转的话，能圈住所有点的正方形边长是随着角度先减后增的，有凸性，可以三分。。。 但是枚举角度计算正方形的话比较麻烦，可以选择旋转平面上的点，使得正方形仍然是水平竖直放置的，因为这样计算正方形的边长比较方便。 如果把点表示成极坐标形式: x=r×cosθ,y=r×sinθ,，θ是极角 那么顺时针旋转 α 角度后： x′=r×cos(θ−α),y=r×sin(θ−α) 化简一下 …

题目链接 题意： 有n个点，表示n个圆的圆心，问一组圆的半径，满足相邻(i,i+1)或者(n,1) 圆相外切。 思路： 我们发现确定第一个半径之后，其他的圆的半径似乎能解出来？ 然后发现，其实只有n为奇数的时候能解出来，n为偶数不行。 那么我们可以奇数偶数分别处理。 对于奇数，直接解出来。式子不写了，很好推。 对于偶数，我们发现，最后会是一个关于r1的二次表达式。 一眼三分。然后训练的时候我就直接三分了。。？？？ 三分的过程中判断一下是否所有圆的半径都满足实际意义。。。 然而这是错得，而且错得很显然。因为。。如果不满足实际意义，是根本没办法判断，该往哪个方向继续三分的。 然而这是错得，而且错得很显然。因为。。如果不满足实际意义，是根 …