【BZOJ1027】【JSOI2007】合金

杨勋上课讲的例题。。刚好在上课的时候刷到这道题

乍一看根本看不出来是计算几何题。。

每一种合金的成分只要确定了其中两种第三种就确定了 那么可以将每一种合金视为二维平面上的一个点

考虑两种合金能够加工出的合金为在两个合金连线上的所有点

三种合金能加工出的为三个点形成的三角形内部的点

那么若干合金能加工出的即为它们凸包内的点

问题转化为从给定点中选若干个点包含所需点

在给定点的每两个点之间, 若所有所需点在这两点的某一侧则连边,然后跑floyd找出最小环

细节很多,需要特判答案为\(1\)以及所有点在一条直线上的情况。

说点什么

  Subscribe  
提醒