International Travel
Time limit2sMemory limit1024 MB
Given three pin circles for a plug and three hole circles for a socket, decide whether the plug can be rigidly moved so each pin fits a matching hole, with the earth pin fixed.
- Level
Hard8 of 10
- Topics
- Geometry, Brute force
- Solved
- No attempts yet
Problem
When you arrive in a new country, one of the first questions is "can I charge my phone here?" Nowadays, voltage is often secondary, because most modern IT equipment is insensitive to voltage. The shapes of outlets and plugs, however, are still a problem.
In this problem, you are given descriptions of an electrical plug and a socket. Determine whether the plug can be inserted into the socket. In this simplified world, each plug pin is a cylinder, and each socket hole is also a cylinder. Sockets have springs that keep the contact tight, so the diameter of a pin may be smaller than the diameter of the matching hole. Pin lengths and hole depths are ignored, so the plug and the socket are each described by three circles.
In both the plug and the socket, one of the three circles is the earth wire, and the two earth circles must match. The other circles are power phases. Most countries use alternating current (AC), so a power pin may be matched to a socket hole in either of the two ways.
Input
The input has six lines. The first three lines describe the plug, and the next three lines describe the socket. The -th line contains three positive integers , , and , which are the coordinates of the center of the pin or hole and its radius. All values are integers not exceeding .
In both the plug and the socket, no two circles intersect or touch. The first pin or hole is the earth wire.
Output
If the plug cannot be inserted into the socket, print NO.
Otherwise, print YES on the first line. On the next three lines, print the new coordinates of the plug pin centers after translating and/or rotating the plug. The answer is accepted if all of the following hold:
- The pairwise distances between the plug pins match the distances in the input within an absolute precision of .
- The output configuration can be obtained from the input plug by translating and/or rotating it.
- Each plug pin radius may be reduced by at most so that the plug fits the hole completely.
If the answer is NO, it is guaranteed that the plug still cannot be inserted even if every plug pin is reduced by .


