Anonymous user
Total circles area: Difference between revisions
Small changes in second C entry: C99, VLAs, less commas, 4 spaces indented, variables scope narrowing
(Used INFINITY as in the second C entry, for uniformity + tags) |
(Small changes in second C entry: C99, VLAs, less commas, 4 spaces indented, variables scope narrowing) |
||
Line 169:
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>
typedef double
typedef struct {
Circle circles[] = {
{ 1.6417233788, 1.6121789534, 0.0848270516},
// ... data snipped for space, copy from previous example.
{ 0.0152957411, 0.0638919221, 0.9771215985}};
inline Fp min(Fp a, Fp b) { return a < b ? a : b; }
inline Fp max(Fp a, Fp b) { return a > b ? a : b; }
inline Fp square(Fp x) { return x * x; }
inline Fp dist(const Fp x0, const Fp y0, const Fp x1, const Fp y1) {
return sqrt(square(x0 - x1) + square(y0 - y1));
}
typedef struct { Fp x0, x1; } Sect;
Fp spans(Circle *c, size_t n_circles,
const Fp ymin, const Fp step, const Fp ymax) {
// Safe if n_circles is not very large.
Sect sects[n_circles];
Fp total = 0;
// GNU C99 extension.
inline void swap_s(const int i, const int j) {
const Sect ss = sects[i];
sects[i] = sects[j];
}
inline void swap_c(const int i, const int j) {
const Circle cc = c[i];
c[i] = c[j];
c[j] = cc;
}
for (size_t j = i + 1; j < n_circles; j++)
swap_c(i, j);
for (int row = 1 + ceil((ymax - ymin) / step); row; row--) {
// Could probably do "y -= step", not sure.
const Fp y = ymin + step * row;
size_t n = n_circles;
for (size_t i = 0; i < n; ) {
if (y >= c[i].y1)
n = i;
else if (y <= c[i].y0) {
const Circle cc = c[i];
for (size_t j = i + 1; j < n_circles; j++)
c[j - 1] = c[j];
n_circles--;
c[n_circles] = cc;
n--;
} else {
const Fp dx = sqrt(c[i].r2 - square(y - c[i].y));
sects[i].x0 = c[i].x - dx;
sects[i].x1 = c[i].x + dx;
i++;
}
}
if (!n)
continue;
for (size_t i = n; i--; ) { // Bubble sort. Important.
bool swapped = false;
for (size_t j = 0; j < i; j++)
if (sects[j].x0 > sects[j + 1].x0) {
swap_s(j, j + 1);
swap_c(j, j + 1);
swapped = true;
}
if (!swapped)
break;
}
Sect *cur = sects;
total += cur->x1 - cur->x0;
for (size_t i = 1; i < n; i++) {
if (sects[i].x1 <= cur->x1)
continue;
total += sects[i].x1 - max(sects[i].x0, cur->x1);
cur = sects + i;
}
}
return total;
}
int main() {
size_t n_circles = sizeof(circles) / sizeof(Circle);
// Remove fully covered circles.
dist(c1->x, c1->y, c2->x, c2->y) + c1->r <= c2->r) {
n_circles--;
*c1 = circles[n_circles];
break;
}
Fp miny = INFINITY, maxy = -INFINITY;
for (size_t i = 0; i < n_circles; i++) {
circles[i].r2 = square(circles[i].r);
circles[i].y0 = circles[i].y - circles[i].r;
circles[i].y1 = circles[i].y + circles[i].r;
miny = min(miny, circles[i].y0);
maxy = max(maxy, circles[i].y1);
}
const size_t s = 1U << 20; // Definitely overkill. Definitely.
const Fp sp = spans(circles, n_circles,
printf("Area = %.10f at\t%d scanlines.\n",
sp / s, (int)((maxy - floor(miny * s) / s) * s));
}</lang>
{{out}}
|