Circle Meets Square

Interview

Time limit1sMemory limit1024 MB

Summary

Given a circle and an axis-aligned square, determine whether they overlap in positive area, touch at a single point, or do not meet.

Level: Medium4 of 10
Topics: Geometry, Math
Solved: No attempts yet

Problem

We all know that a round peg cannot fit into a square hole. Asking you to do so in this contest would be cruel and unusual punishment, which the Eighth Amendment to the United States Constitution bans. A more reasonable problem, one the Framers probably never considered, is determining whether a given circle and square overlap in a region of positive area, touch at a single point, or do not touch at all.

The Framers of the US Constitution and the UCF Programming Team coaches want to know, for a given circle and square, whether the two overlap in positive area, touch, or do not touch at all. Write a program that helps them.

Given the description of a square and a circle in the Cartesian plane, determine whether their intersection has positive area (overlap), is a single point (touch), or does not exist.

Input

The first line contains three integers x, y, and r, the x and y coordinates and the radius of the circle. $-1{,}000 \le x \le 1{,}000$ , $-1{,}000 \le y \le 1{,}000$ , and $0 < r \le 1{,}000$ .

The second line contains three integers tx, ty, and s, where (tx, ty) is the bottom left corner of the square and s is its side length. $-1{,}000 \le t_x < 1{,}000$ , $-1{,}000 \le t_y < 1{,}000$ , and $0 < s \le 1{,}000$ . The top right corner is (tx+s, ty+s), and the sides are parallel to the x and y axes.

Output

Print 0 if the circle and square do not touch. Print 1 if they touch at a single point. Print 2 if they overlap in positive area.

Hint

Pictures of the sample inputs



First sample	Second sample	Third sample

Examples3

Example 1
Input
```
0 0 5
2 3 1
```
Expected output
```
2
```
Example 2
Input
```
0 0 5
5 0 6
```
Expected output
```
1
```
Example 3
Input
```
0 5 4
-1 -1 1
```
Expected output
```
0
```