/* Dejan Belic */ #include #include #include #include #include void random_point(double point[2], double min_x, double max_x, double min_y, double max_y) { point[0] = ((double) rand() / RAND_MAX) * (max_x - min_x) + min_x; point[1] = ((double) rand() / RAND_MAX) * (max_y - min_y) + min_y; } int inside_circle(double point[2], double circle[3]) { double dx = point[0] - circle[0]; double dy = point[1] - circle[1]; double r = circle[2]; return dx * dx + dy * dy <= r * r; } int main() { // Setup MPI int rank; int size; MPI_Init(NULL, NULL); MPI_Comm_size(MPI_COMM_WORLD, &size); MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Read inputs int n; if (rank == 0) scanf("%d", &n); MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD); if (n < 0) { // Wrong input if (rank == 0) printf("%lf\n", 0.0); MPI_Finalize(); return 0; } double min_x = 0; double max_x = -1; double min_y = 0; double max_y = -1; double circles[n][3]; if (rank == 0) { double x, y, r; for (size_t i = 0; i < n; i++) { scanf("%lf%lf%lf", &x, &y, &r); circles[i][0] = x; circles[i][1] = y; circles[i][2] = r; if (x - r > min_x) min_x = x - r; if (y - r > min_y) min_y = y - r; if (x + r < max_x || max_x == -1) max_x = x + r; if (y + r < max_y || max_y == -1) max_y = y + r; } } // Synchronize processes MPI_Bcast(&min_x, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD); MPI_Bcast(&min_y, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD); MPI_Bcast(&max_x, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD); MPI_Bcast(&max_y, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD); if (max_x < min_x || max_y < min_y) { // No intersection if (rank == 0) printf("%lf\n", 0.0); MPI_Finalize(); return 0; } MPI_Bcast(circles, 3 * n, MPI_DOUBLE, 0, MPI_COMM_WORLD); // Preform calculations int N = 10000000; int inside_region = 0; srand(rank * time(0)); double point[2]; for (size_t i = rank; i < N; i += size) { random_point(point, min_x, max_x, min_y, max_y); int is_inside_region = 1; for (size_t j = 0; j < n && is_inside_region; j++) is_inside_region = is_inside_region && inside_circle(point, circles[j]); inside_region += is_inside_region; } // Combine results int total_inside_region; MPI_Reduce(&inside_region, &total_inside_region, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD); if (rank == 0) { double square_area = (double) (max_x - min_x) * (max_y - min_y); double hit_ratio = (double) total_inside_region / N; double area = hit_ratio * square_area; printf("%.3lf\n", area); } MPI_Finalize(); return 0; }