Two Lights in a Square Room
Time limit40sMemory limit512 MB
Given two point lights and up to 50 circular pillars inside a square, find the area lit by neither, by red only, by green only, and by both.
- Level
Hard8 of 10
- Topics
- Geometry, Implementation, Divide and conquer, Brute force
- Solved
- No attempts yet
Problem
A large square room holds two point light sources. One is red and the other is green. The room also holds n circular pillars.
Light travels in straight lines and the walls and the pillars absorb it. A pillar lets no light through, so it casts a shadow. Some places in the room get no light at all (black), some get light from exactly one of the two sources (red or green), and some get light from both (yellow). Compute the total area of each of the four colors. The part covered by the pillars counts toward none of the four areas.
Input
The first line contains the number of test cases T.
Each test case is given in this order.
- One line with the coordinates x, y of the red light source.
- One line with the coordinates x, y of the green light source.
- One line with the number of pillars n.
- n lines, each describing one pillar with x, y, r. That pillar is the disk with center (x, y) and radius r.
The room is the square . The pillars, the walls of the room and the two light sources do not overlap and do not touch.
Limits
- Every number in the input is an integer.
Output
Print five lines for each test case. The first line is Case #X:, where X is the number of the test case, counting from 1. Then print the black, red, green and yellow areas in this order, one per line.
Case #X:
black area
red area
green area
yellow area
Round every area to four digits after the decimal point. Print 0.0000 for an area of zero.