题解：P2987 [USACO10MAR] StarCowraft G

_2022gdgzby01 · 2024-09-18 13:27:41 · 题解

思路

首先我们发现，我们能够把三种单位的战斗力同时乘以一个数而不改变结果。因此，不妨设第三种单位的战斗力 S_3=1，出于方便，不妨设 x=S_1,y=S_2。

对于一场比赛，我们能够写出一个类似这样的式子：j_1x+j_2y+j_3\le b_1x+b_2y+b_3。

整理后得到一个类似这样的式子：ax+by\le c 。

这就是半平面，所以做法就很简单了：对所有测试点的半平面求交，其交集是一个凸多边形。将其所有顶点求出。在试图判断一次新的战斗时，显然该场战斗对应于一条直线，如果凸多边形人所有顶点均在直线一侧，那么该战斗的结果是确定的，否则不定。

注意，那个“单位之差不超过 100 倍”的条件也是要写出来的。