Under construction

Still being built. Things may change

3-Sided Dice

Time limit1sMemory limit128 MB

Summary
Determine whether a target 3-outcome probability vector lies in the convex hull (with strictly positive weights) of three given dice's probability vectors.
Level

Medium5 of 10

Topics
Geometry, Math, Simulation
Solved
No attempts yet

Problem

Every autumn the organizers of the Southwestern Europe Dice Simulation Contest are busy again. This year you must simulate a 3-sided die that produces each of three outcomes — written 11, 22, and 33 — with prescribed probabilities, using three dice from a given set. The simulation works like this: pick one of the three given dice at random, roll it, and report its outcome. You are free to choose the probability of picking each of the three dice, as long as every one of those probabilities is strictly greater than zero. Before handing out the materials, the organizers must check that the task is actually solvable.

For instance, suppose you must simulate a die that yields outcomes 11, 22, and 33 with probabilities 3/103/10, 4/104/10, and 3/103/10, and you are given three dice where the ii-th die always yields outcome ii. Then you can reproduce the target die by picking the first die with probability 3/103/10, the second with probability 4/104/10, and the third with probability 3/103/10.

Input

The input consists of several test cases, separated by single blank lines. Each test case has four lines: the first three describe the three dice you are given, and the last describes the die you must simulate. Each of the four lines contains three space-separated integers between 00 and 1000010000 inclusive. The three numbers on a line add up to 1000010000 and equal 1000010000 times the probability that the die on that line yields outcome 11, 22, and 33, respectively.

The input ends with a line containing the number zero three times (also preceded by a blank line).

Output

For each test case, print a line containing YES if the desired die can be produced from the given dice, or NO otherwise.

Examples3

  1. Example 1

    Input
    0 0 10000
    0 10000 0
    10000 0 0
    3000 4000 3000
    
    0 0 10000
    0 10000 0
    3000 4000 3000
    10000 0 0
    
    0 0 0
    
    Expected output
    YES
    NO
    
  2. Example 2

    Input
    10000 0 0
    0 10000 0
    0 0 10000
    10000 0 0
    
    0 0 0
    
    Expected output
    NO
    
  3. Example 3

    Input
    10000 0 0
    0 10000 0
    0 0 10000
    4000 3000 3000
    
    0 0 0
    
    Expected output
    YES