ACM

POJ 2187 Beauty Contest(计算几何-旋转卡壳)

POJ 2187 Beauty Contest(计算几何-旋转卡壳)
题意:给出一个多边形,求出多边形最远两点距离的平方。题解:旋转卡壳模板题,先求凸包再用Andrew求最远点对即可。代码:StatusAcceptedTime219msMemory3128kBLength2774LangG++#include <iostream> #include <cstdio> #include <cstring&... 继续阅读 »
ACM

POJ - 1113 Wall(计算几何-凸包)

POJ - 1113 Wall(计算几何-凸包)
题意:给出一个多边形,在距离这个多边形最低为L的地方建立一堵墙,求这墙的周长。题解:对圆角加起来为什么是个圆很不理解,所以就看了kuangbin巨巨的题解。这道题的答案是凸包周长加上一个圆周长,即包围凸包的一个圆角多边形,但是没弄明白那些圆角加起来为什么恰好是一个圆。每个圆角是以凸包对应的顶点为圆心,给定的L为半径,与相邻两条边的切点之间的一段圆弧。每个圆弧的两条半径夹角与对应的凸包的内角互补。假... 继续阅读 »