Problem 1002: Antialias

(ACM S.E. U.S.A. Regional 2003, problem 2)

Description

While actors, directors, and screenwriters work to make good movies, engineers and computer scientists work to make movies look good. Jagged edges can result from problems when the edge of an object does not align perfectly with the edges of the pixels. Consider the group of pixels below with an edge of a polygon shown. If the pixels are just turned on or off, a jagged edge results.

To reduce the jagged effect, you can antialias the edges of a filled counter-clockwise oriented polygon, by using an appropriate gray-scale for the border pixels. To determine the gray-scale for these border pixels, we need to find the percentage of the area of the pixel falling inside the polygon.

We will consider a pixel as being a horizontally aligned, unit square. To simplify the problem, we assume that exactly one polygon edge-segment cuts a target pixel. We are given the coordinate of the point where the edge-segment enters the pixel (entry point), and the point where the edge- segment exits the pixel (exit point) in coordinates relative to the lower-left corner of the pixel. Thus, given these two points, we want to find the area of the pixel to the left of the edge-segment (looking in the direction of the edge-segment).

In the diagram above, the entry point is at (0.0, 0.25) and the exit point is at (1.0, 0.5). Your task is to find the area of the pixel to the left of the edge-segment (i.e., the cross-hatched area), which, in this case, is 0.625. If the edge-segment had been specified as going in the opposite direction (i.e., entry and exit points reversed) the area of the pixel to the left of the edge-segment would be the unshaded area, equal to 0.375.

Input Format

The first line of a data set consists of the x- and y-coordinate of the entry point of the edge- segment. The second line contains the x- and y-coordinates of the exit point, which is guaranteed to be non-coincident with the entry point. All x- and y-coordinates are numbers in the range from 0 to 1, given to a precision of at most 4 decimal places. (Other than in the case of the end-of-data flag, at least one of the x- and the y-coordinate of each pixel will be either 0 or 1since the entry and exit points lie on the border of the pixel).

A coordinate value of (0.5, 0.5) for the entry point flags the end of data, and should not be processed.

Output Format

For each data set there is one line of output in the form
Pixel n has area a to the left of the edge-segment
where n is the number of the data set (starting at 1), and a is the calculated area rounded to 4 decimal places.

Sample Input

Sample Output

Pixel 1 has area 0.6250 to the left of the edge-segment
Pixel 2 has area 0.3750 to the left of the edge-segment
Pixel 3 has area 0.1250 to the left of the edge-segment