Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1530
Measuring the area of a certain shape is an important part of certain geometric problems. When the shape becomes complex it often becomes very difficult to measure the area of that geometric shape. In some of these cases some randomized algorithms helps us immensely to find the area roughly. In this problem we will find such an area with randomized algorithm. Look at the picture on the right. ABCD is a square whose sides are a. A circle is drawn (1/4 th of a circle I should say) considering A as its center. Its radius is a. Three similar circles are drawn considering B, C, D as centers. Using an algorithm based on random numbers (The random number generator may be biased) you will have to find the area of the striped region. The idea is that you will be given N pairs of random coordinates within the rectangle. If M of them are within the striped region then the approximate area of the striped region A = M ∗ a ∗ a/N. You are to find the approximate area using this concept. Input The input file contains several sets of inputs. The description of each set is given below. The first line of each set contains two integers N (N can always be written in the form 10k where k is a non-negative integer less than 6), a (100 > a ≥ 10). Each of the next N lines contains two floatingpoint numbers, which indicates the coordinate of a point. These floating-point numbers always have seven digits after the decimal point and the coordinates are always within the rectangle. Points just on the boundaries of the striped region are considered within the striped region. Points just outside are considered out of the striped region and vice versa. Assume that the lower left corner of the rectangle is (0, 0) and top right corner is (a, a) as shown in the figure above. Input is terminated by a set whose N is zero. Output For each of input you should produce one line of output. This line should contain the area of the striped region according to the formula specified above. Your answer must be exact and no floating-point errors will be tolerated. That means precision of calculation must be infinite or precision error must be zero. Output numbers should always have five digits after the decimal point.
Sample Input 1 10 5.0000000 5.0000000 0 0
Sample Output 100.00000
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
struct point {
double x, y;
point() { x = y = 0.0; }
point(double _x, double _y) : x(_x), y(_y) {}
};
double dist(point p1, point p2) { // Euclidean distance
// hypot(dx, dy) returns sqrt(dx * dx + dy * dy)
return hypot(p1.x - p2.x, p1.y - p2.y);
}
int main() {
int n, a;
while(scanf("%d %d",&n,&a),(n+a)) {
int m = 0;
vector < point> corners{
point(0,0), point(a,0), point(a,a), point(0,a)
};
for(int i=0;i < n;i++){
point p;
scanf("%lf %lf",&p.x,&p.y);
bool within = true;
for(auto& corner : corners){
double euc = dist(p, corner);
if(euc > a) {
within = false;
break;
}
}
if(within) m++;
}
printf("%.5f\n", (double)m/n*a*a);
}
}
Input
5.0000000 5.0000000
0 0
Output
Demonstration
UVA Online Judge solution - 10589-Area - UVA Online Judge solution in C,C++,java