Humanity's Last Code Exam / 2013_J / Pollution Solution

## Problem Statement

As an employee of Aqueous Contaminate Management, you must monitor the pollution that gets dumped (sometimes accidentally, sometimes purposefully) into rivers, lakes, and oceans. One of your jobs is to measure the impact of the pollution on various ecosystems in the water such as coral reefs, spawning grounds, and so on.

The model you use in your analysis is illustrated in Figure J.1. The shoreline (the horizontal line in the figure) lies on the x-axis with the source of the pollution located at the origin (0,0). The spread of the pollution into the water is represented by the semicircle, and the polygon represents the ecosystem of concern. You must determine the area of the ecosystem that is contaminated, represented by the dark blue region in the figure.

### Input

The input consists of a single test case. A test case starts with a line containing two integers n and r, where 3≤n≤100 is the number of vertices in the polygon and 1≤r≤1000 is the radius of the pollution field. This is followed by n lines, each containing two integers x_(i),y_(i), giving the coordinates of the polygon vertices in counter-clockwise order, where −1500≤x_(i)≤1500 and 0≤y_(i)≤1500. The polygon does not self-intersect or touch itself. No vertex lies on the circle boundary.

### Output

Display the area of the polygon that falls within the semicircle centered at the origin with radius r. Give the result with an absolute error of at most 10^(−3).

### Sample Input 1

## Problem Statement

As an employee of Aqueous Contaminate Management, you must monitor the pollution that gets dumped (sometimes accidentally, sometimes purposefully) into rivers, lakes, and oceans. One of your jobs is to measure the impact of the pollution on various ecosystems in the water such as coral reefs, spawning grounds, and so on.

The model you use in your analysis is illustrated in Figure J.1. The shoreline (the horizontal line in the figure) lies on the x-axis with the source of the pollution located at the origin (0,0). The spread of the pollution into the water is represented by the semicircle, and the polygon represents the ecosystem of concern. You must determine the area of the ecosystem that is contaminated, represented by the dark blue region in the figure.

### Input

The input consists of a single test case. A test case starts with a line containing two integers \( n \) and \( r \), where \( 3 \leq n \leq 100 \) is the number of vertices in the polygon and \( 1 \leq r \leq 1000 \) is the radius of the pollution field. This is followed by \( n \) lines, each containing two integers \( x_i, y_i \), giving the coordinates of the polygon vertices in counter-clockwise order, where \( -1500 \leq x_i \leq 1500 \) and \( 0 \leq y_i \leq 1500 \). The polygon does not self-intersect or touch itself. No vertex lies on the circle boundary.

### Output

Display the area of the polygon that falls within the semicircle centered at the origin with radius \( r \). Give the result with an absolute error of at most \( 10^{-3} \).

### Sample Input 1