[UVA][幾何] 10613 - Mushroom Misery
Problem E
Mushroom Misery
Input: Standard Input
Output: Standard Output
Time Limit: 2 Seconds
The Institute of Ubiquitousness in Lichtenstein, LIU, conducts a project where the effect of a special type of fungi, sphera carnelevarium, is studied. This fungus is very special, since it grows in a circular fashion from its centre, without interference from other objects or other individuals.
Until now, the impact of this forest-living creature has been measured by examining a grid consisting of n*n squares of size 1 m2. A grid is considered affected, if fungi are present in the square, otherwise it is considered clean. Grids, where the fungus merely touches the border of the square are not considered affected.
Of course, the task of examining grids is tedious and now unnecessary, since Prof. Muggel discovered that the grow rate is exactly 2.718281828 m/day. Now, counting the number of affected squares should be like a stroll in the park, right? Since there are a lot of old data, which will be compared to the new data, the rules of counting the squares must be the same. Do not use data types with unnecessary low precision in your calculations.
Fig: This figure corresponds to the sample input
Input
On the first line of input there is one integer, N <= 10, giving the number of test cases in the input. After this line, N test cases follows. Each test case starts with a line containing two integers size, n
such that 0 < size <= 1000000, 0 < n <= 1000, where size is the size of the grid in meters and n is the number of individuals in the test grid. After this line, n lines follows, each line consisting of three decimal number, 0 <= x <= size, 0 <= y <= size, 0 < r<= size, where x and y are the zero-based coordinates of the center of the individual and r is the (estimated) radius in meters.
Output
For every test case, output one line containing the number of affected squares (a number between 0 and size2). However, the number of affected squares is always less than 1000000000 (109).
Sample Input Output for Sample Input
|
2 1 2 3 1 1.5 1.5 0.44 5 3 2 2 1.31 1.5 2.5 0.5 3 3 0.94 |
1 13
|
Problem setter: Andreas Björklund, Source: Swedish National Contest
其實我有點看不懂學長在寫什麼，不過如果 r < size 的話，也有可能速度是很慢的，
剛好每個 r 都不大，然後對每個單位 x = ? 拉出一個涵蓋的線段，因此要拉 2r 個，
將全部的圓都分解後，然後對 不同的 x 依序計數。
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
struct Seg {
int st, ed, x;
void set(int a, int b, int c) {
st = a, ed = b, x = c;
}
};
Seg S[2000000];
int Ssize;
bool cmp(Seg a, Seg b) {
if(a.x != b.x)
return a.x < b.x;
return a.st < b.st;
}
void cut2seg(double x, double y, double r, int size) {
int L, R, M, i, st, ed;
L = max(0, (int)floor(y-r));
R = min(size, (int)ceil(y+r));
M = (int)floor(y);
for(i = L; i < M; i++) {
st = max(0, (int)floor(x-sqrt(r*r-(y-i-1)*(y-i-1))));
ed = min(size, (int)ceil(x+sqrt(r*r-(y-i-1)*(y-i-1))));
S[Ssize++].set(st, ed, i);
}
st = max(0, (int)floor(x-r));
ed = min(size, (int)ceil(x+r));
S[Ssize++].set(st, ed, M);
for(i = M+1; i < R; i++) {
st = max(0, (int)floor(x-sqrt(r*r-(y-i)*(y-i))));
ed = min(size, (int)ceil(x+sqrt(r*r-(y-i)*(y-i))));
S[Ssize++].set(st, ed, i);
}
}
int main() {
int t, n, size;
double x, y, r;
int i, j;
scanf("%d", &t);
while(t--) {
Ssize = 0;
scanf("%d %d", &size, &n);
for(i = 0; i < n; i++) {
scanf("%lf %lf %lf", &x, &y, &r);
cut2seg(x, y, r, size);
}
sort(S, S+Ssize, cmp);
int res = 0, pre = 0;
int L, R;
for(i = 0; i <= Ssize; i++) {
if(S[i].x != S[pre].x || i == Ssize) {
L = S[pre].st, R = S[pre].ed;
for(j = pre; j < i; j++) {
if(S[j].st <= R) {
if(S[j].ed >= R)
R = S[j].ed;
} else {
res += R-L;
L = S[j].st, R = S[j].ed;
}
}
res += R-L;
pre = i;
}
}
printf("%d\n", res);
}
return 0;
}