6398专题

HDU 6398 Pizza Hub(计算几何 三角形放置)

http://acm.hdu.edu.cn/showproblem.php?pid=6398 题意: 给一个可旋转的三角形,求一个宽为W的矩形的最小高度,使得这个三角形可以塞进去 解析: 一定有一个点在边上,所以枚举每个点P做(吉如一jls推荐的旋转平移流) 平移坐标系使得P落在原点 选择第二个点K,尝试这样放 如果不行,就这样放 或者这样 通过K的旋转,计算得到最后一