|
Setup
A farmer whose crops are infested with aphids has opted for an organic approach to aphid control: Ladybugs. In an experiment, the farmer releases a popuation of aphids on one plant and a population of ladybugs on another (not necessarily distinct) plant. These two populations spread out to infect nearby plants. After some time, the farmer closely inspects those plants which have been infected by both the aphids and the ladybugs. We are concerned with the number of plants which have been so infected. The farmer’s field can be modeled as an xy-plane with a plant at each lattice point, that is, at each point (a, b) where a and b are integers. The plants infected by the two insects are those which lie inside the intersection of two circles. |
Challenge
We may assume that the set of plants infected by a given insect are those lying within a circle of radius for some integer r, centered at some lattice point (a, b). There will be no plants on the boundary of the circle; each plant will be at least 0.0003 from the boundary. Each of a, b and r will be in the range –10,000 to 10,000. Each input instance will be in the form: X1 Y1 radius12 X2 Y2 radius22 (Note that the square of the radius will be given.) and there will be at most 1000 instances. The first line of the input will contain the number of instances. The output should be the number of lattice points lying in the intersection of the circles. Sample Input 4 0 0 1 4 4 1 0 0 3 0 0 3 0 0 3 2 0 7 1 3 43 4 7 63 Sample Output 0 9 6 91 |
|
Deadline
The deadline for submission is Monday, October 10, 2005 Many contests and challenges offer cash awards to the winners, leaving them feeling cheap, as if their talent was available to anyone at any time for a price! This challenges offers you points! Each team or individual submitting a program is eligible for points. See rules for details. |
Submission
Email code to: challenge@cs.ecu.edu |