Problem J
Joining Flows
The heart of the factory is the Chocolate River, where raw molten chocolate flows from $k$ chocolate-producing faucets, to outlets where different types of pralines and choclate bars are made. The $i$’th of the $k$ chocolate faucets produces chocolate at some fixed temperature $t_ i$, and the amount of chocolate flowing from the faucet can be adjusted to any value between $a_ i$ and $b_ i$ millilitres per second. Suppose the $k$ taps are adjusted to produce $x_1, x_2, \ldots , x_ k$ millilitres of chocolates per second respectively (where $a_ i \le x_ i \le b_ i$). Then the total flow in the Chocolate river is $x_1 + x_2 + \ldots + x_ k$, and its temperature is the weighted average
\[ \frac{x_1 t_1 + x_2t_2 + \ldots + x_ kt_ k}{x_1 + x_2 + \ldots + x_ k} \](each faucet produces grade A quality chocolate which instantly mixes with the chocolate from the other faucets).
Each type of praline and chocolate bar produced at the factory requires the Chocolate River to be adjusted to have a specific temperature and flow level. Charlie recently came across a long list of new praline recipes, and would now like to figure out which of these are even possible to make at the factory. Write a program to determine, for each of the new recipes, if its required temperature and flow level is possible to achieve with some setting of the $k$ faucets.
Input
The first line of input contains an integer $k$ ($1 \le k \le 10$), the number of taps. Then follow $k$ lines, describing the taps. The $i$’th of these lines contains the three integers $t_ i$, $a_ i$, and $b_ i$ ($0 \le t_ i \le 10^6$, $0 \le a_ i \le b_ i \le 10^6$) describing the $i$’th faucet.
Next follows a line containing an integer $r$ ($1 \le r \le 10^5$), the number of new recipes to check. Then follows $r$ lines, each describing a recipe. A recipe is described by two integers $\tau $ and $\phi $ ($0 \le \tau \le 10^6$ and $1 \le \phi \le 10^6$), where $\tau $ is the chocolate temperature and $\phi $ the chocolate flow needed for this recipe.
Output
For each of the $r$ recipes, print one line with the string “yes” if it is possible to achieve the desired combination of chocolate temperature and flow, and “no” otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 50 0 100 100 50 100 3 20 75 75 150 75 90 |
no yes no |
