Molecules
Time limit2sMemory limit512 MB
Given a connected graph with some vertex positions fixed, find positions for the rest so each unknown vertex sits at the average of its neighbors; any valid solution is accepted.
- Level
Hard8 of 10
- Topics
- Graph, Math, Implementation, Greedy
- Solved
- No attempts yet
Problem
A molecule consists of atoms held together by chemical bonds. Each bond links two atoms. Each atom may be linked to multiple other atoms, each through a separate chemical bond. All atoms in a molecule are connected to one another through chemical bonds, directly or indirectly.
The chemical properties of a molecule are determined not only by how pairs of atoms are connected through chemical bonds, but also by the physical locations of the atoms within the molecule. Chemical bonds can pull atoms toward each other, so it is sometimes difficult to determine the locations of the atoms given the complex interactions of all the chemical bonds in a molecule.
You are given a description of a molecule. Each chemical bond connects two distinct atoms, and there is at most one bond between each pair of atoms. The coordinates of some of the atoms are known and fixed, and the remaining atoms naturally move to locations such that each atom is at the average of the locations of the neighboring atoms linked to it through chemical bonds. For simplicity, the atoms in the molecule lie on the Cartesian xy-plane.
Input
The first line of input contains two integers n (2 ≤ n ≤ 100), the number of atoms, and m (n − 1 ≤ m ≤ n(n−1)/2), the number of chemical bonds.
The next n lines describe the locations of the atoms. The ith of these lines contains two integers x and y (0 ≤ x, y ≤ 1 000 or x = y = −1), the x and y coordinates of the ith atom. If both coordinates are −1, the location of this atom is unknown.
The next m lines describe the chemical bonds. The ith of these lines contains two integers a and b (1 ≤ a < b ≤ n), meaning there is a chemical bond between atom a and atom b.
At least one atom has a fixed location.
Output
Display n lines describing the final location of each atom. On the ith line, display two numbers x and y, the final coordinates of the ith atom. If there are multiple solutions, any of them is accepted. A solution is accepted if the coordinates of each unknown atom and the average coordinates of all the neighboring atoms linked to it through chemical bonds differ by at most 10−3. Multiple atoms may share the same coordinates.