This page is still under construction.

Parts of this page are still being built. What you see may change.

Dragon Fantasy

Time limit8sMemory limit512 MB

Summary
Given hero and demon positions and up to 20 crystals, decide whether the hero can collect all crystals before the expanding miasma swallows them.
Level

Medium7 of 10

Topics
Binary search, Math, Geometry, Simulation
Solved
No attempts yet

Problem

The peace that seemed to last forever ended abruptly. The Demon King, sealed away long ago, has finally revived. But just as the world is about to be covered in darkness, one hero appeared. That hero set out on a journey to collect the legendary crystals scattered across the world. Legend says that if all the crystals are collected, one can summon the legendary Dragon God, who grants any wish. With the Dragon God's power, it should be possible to defeat the Demon King.

The crystals are scattered across the world. The hero must collect them one by one by hand. If anyone other than the hero gets a crystal, the Demon King's minions might take it away. The hero can move a Euclidean distance of 1 per day.

There is one serious problem. The Demon King constantly gives off a dark miasma, and any place contaminated by it becomes a dead land where no one can set foot. Even the hero cannot enter such a place. Moreover, the miasma spreads outward in concentric circles over time, so the area the hero can move through shrinks as time passes. The miasma is confirmed to spread a Euclidean distance of 1 per day. A crystal on the boundary of the miasma cannot be taken by the hero. It is also known that the newly revived Demon King does not move, saving up his power.

The hero must get the crystals as soon as possible. But if collecting all the crystals is impossible, he will have to think of another way. So, given the hero's starting position, the position where the Demon King revived, and the positions of the crystals, write a program to determine whether all the crystals can be collected.

By the way, the hero never gets tired. And he never sleeps. He keeps moving and collecting crystals until he has gathered them all and saved the world!!

Input

The input consists of multiple test cases. The first line of each test case gives five integers n (0 < n ≤ 20), hx, hy, dx, dy. n is the number of crystals, (hx, hy) is the hero's position at the moment the Demon King revives, and (dx, dy) is the position where the Demon King revived. The following n lines each give two integers cx, cy, the position of a crystal. The input ends when n = hx = hy = dx = dy = 0, which is not part of the test cases.

All coordinates in the input are guaranteed to be integers with absolute value at most 1000.

Output

For each test case, print "YES" if all the crystals can be collected, and "NO" otherwise.

Examples1

  1. Example 1

    Input
    2 0 0 10 10
1 1
4 4
2 0 0 10 10
1 1
6 6
2 0 0 10 10
1 1
5 5
0 0 0 0 0
    Expected output
    YES
NO
NO