about 3 years ago

题目大意请走(中文题自己看题T^T)

分析

对于每一个原材料,很显然是没有用的。因为所有的,所以我们只需要记录即可。
将每个点加入平面中,我们的目的就是选出一个最少点的多边形使得询问的每个点都在这个多边形内。
怎么做呢?我们对于每条有向边,如果所有的询问点都在其右侧的话,将其加入边集中,最后再用floyd跑一遍最小环即可。是不是很简单。。。
但你还是Too Simple。如果所有的询问点都在同一个给定点上,输出。如果所有询问点都在同一条边上,输出。特判了以上两种情况后,你在判断所有询问点是否在一条边的右侧时,必须要么在这条边的绝对右侧,要么在这条线段上。加上了以上判断后就可以A啦!
bzoj1027.cpp

← 平面区域(bzoj1035) 后缀自动机小结 →
 
comments powered by Disqus