2014
02-24

# Fairies’ Defence

There are n fairies living happily in the Fairyland. One day, when the fairies are playing games, they are suddenly stuck in the sky and cannot move anymore! "Your moving abilities are sealed by my magic. Be ready to defense my attack!" a terrible voice came out, "I’ll appear in the cube (0, 0, 0)-(a, b, c), rush to the nearest fairy and then, make my assault with all my power!"
Since all the fairies cannot move any more, the only chance is to redistribute their defense powers according to their dangerousness. Formally, the defense power one fairy gains should be proportional to its probability to be attacked by the unknown fierce creature.
Write a program to compute the probability to be attacked, for every fairy. You may assume that the probability density of the attacker’s initial position is the same everywhere in the cube; if there are at least two fairies closest (having the minimal Euclidean distance) to the initial position, any one may be attacked.

The input consists of several test cases. The first line of each case contains four integers, n, a, b, c (2 ≤ n ≤ 20, 1 ≤ a, b, c ≤ 1000). This is followed by n lines, each containing three integers x, y, z (0 ≤ x ≤ a, 0 ≤ y ≤ b, 0 ≤ z ≤ c), the coordinates of the fairies. No two fairies occupy the same position. The last test case is followed by a single zero, which should not be processed.

The input consists of several test cases. The first line of each case contains four integers, n, a, b, c (2 ≤ n ≤ 20, 1 ≤ a, b, c ≤ 1000). This is followed by n lines, each containing three integers x, y, z (0 ≤ x ≤ a, 0 ≤ y ≤ b, 0 ≤ z ≤ c), the coordinates of the fairies. No two fairies occupy the same position. The last test case is followed by a single zero, which should not be processed.

2 3 3 3
1 1 1
2 2 2
2 7 2 10
1 1 6
3 1 6
0

Case 1: 0.500 0.500
Case 2: 0.286 0.714

HDU_2933

具体的思路可以参考《浅谈数形结合思想在信息学竞赛中的应用》

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXD 100010
typedef long long LL;
int N, K, A[MAXD], q[MAXD];
void cin(int &x)
{
char ch;
while(ch = getchar(), ch < '0' || ch > '9');
x = ch - '0';
while(ch = getchar(), ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + ch - '0';
}
void init()
{
int i;
A[0] = 0;
for(i = 1; i <= N; i ++) cin(A[i]), A[i] += A[i - 1];
}
void solve()
{
int i, j, x, y, z, front, rear;
double ans = 0;
front = rear = 0;
q[rear ++] = 0;
for(i = K; i <= N; i ++)
{
while(front < rear - 1)
{
x = q[front], y = q[front + 1];
if((LL)(A[i] - A[x]) * (i - y) > (LL)(A[i] - A[y]) * (i - x)) break;
++ front;
}
ans = std::max(ans, (double)(A[i] - A[q[front]]) / (i - q[front]));
q[rear] = i - K + 1;
while(front < rear - 1)
{
x = q[rear - 2], y = q[rear - 1], z = q[rear];
if((LL)(A[z] - A[y]) * (y - x) > (LL)(A[y] - A[x]) * (z - y)) break;
-- rear, q[rear] = q[rear + 1];
}
++ rear;
}
printf("%.2f\n", ans);
}
int main()
{
while(scanf("%d%d", &N, &K) == 2)
{
init();
solve();
}
return 0;
}