# UVa 10885

## 10885 - Martin the Gardener[edit]

## Summary[edit]

Find a set of 13 points on a 2-dimensional Cartesian plane, such that:

- the points have integer coordinates
- the distance between any two points is an integer
- no three points lie on the same straight line.

## Explanation[edit]

We can weaken the first two conditions. Suppose, that we have found a set of 13 points with rational coordinates and *rational* distances between every two of them. Let L be the LCM of denominators of all coordinates and distances. Then, by multiplying coordinates of every point by L, we'll get a set of points with integer coordiantes and integer distance between every two of them.

Now, let's impose an additional constraint on the set of points. We'll be looking for a set of points, all of which lie on the same circle. It's easy to see, that every three points from this set will not lie on the same line, because a straight line intersects a circle in at most two points.

As a simplification, we may further assume that the points lie on a circle of unit radius, whose center is at the origin. Then the coordinates of the points may be written in the following form:

, ,

The distance between i-th and j-th points is:

If we add the constraint, that every and are rational, then the points will have rational coordiantes, and distance between any two of them will be rational, too.

Let , for some integers and .

Then . This value will be rational if , for some integer .

So, what we are now really looking for if is just a set of pythagorean triples , that is integers, which satisfy the equation: .

Having found a few of them (by e.g. brute force enumeration), you can express the coordinates of points:

, .

## Output[edit]

0 180 0 3876 432 0 432 4056 1615 0 1615 4056 2047 180 2047 3876 2511 3528 2511 528 2880 1020 2880 3036 3136 2028