Skip to content

Computational Geometry

  • Pick公式：平面上以格子点为顶点的简单多边形，如果边上的点数为on，内部的点数为in，则它的面积为area=on/2+in-1
  • 二分法在几何计算中是常用的。

Similar Polygons

看两个多边形是否相似，只需要判断每对应两点的距离是否成比例。注意：不只是相邻点，不相邻的也要判断。

多维坐标最远曼哈顿距离点对

对于两维的情况，两个点(x1,y1)(x2,y2)之间的距离为|x1-x2|+|y1-y2|，可能取±(x1-x2)±(y1-y2)，假如真实的情况是(x1-x2)+(y1-y2)，那个在其他情况下算出来的关于这两个点的最大距离肯定比这个小（去掉绝对值符号了），然而±(x1-x2)±(y1-y2)可以写成(x1±y1)-(x2±y2)。把于是(x±y)看成一个点的权值。只要枚举每一维的分量前面的符号即可，对于每一次枚举算出所有的n个点中权值最大的和最小的，求差，更新答案求最大即可。