|
задача fire розвязується дуже просто.
в нас на початку було X*Y*Z станцій, тому нехай ans = X*Y*Z.
тепер для всіх ударів метеоритів ми віднімаємо від ans наступне
якщо удар x y 0 => ans -= z;якщо x 0 z => ans -= y;якщо 0 y z => ans -= x;
далі знаходимо всі перетини пострілів та зберігаємо їх в масиві їхніх координат.
сортуємо масив.
далі якщо точка в масиві зустріається 1 раз то ans++, якщо 3 рази то ans+=2.
відповідб в ans.
а ось і тескст!
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define uchar unsigned char
#define MAXP 155
typedef struct ttype {
long x, y, z;
uchar w;
} ttype;
typedef struct ntype {
long x, y, z;
} ntype;
ttype a[MAXP];
ntype points[MAXP * MAXP];
long x, y, z, p, i, j, h;
double ans;
long max(long *a,long *b)
{
if (*a > *b)
return (*a);
else
return (*b);
}
long cmp(ntype *a,ntype *b)
{
if (a->x < b->x)
return 1;
else if (a->x > b->x)
return 0;
else {
if (a->y < b->y)
return 1;
else if (a->y > b->y)
return 0;
else {
if (a->z < b->z)
return 1;
else if (a->z > b->z)
return 0;
else
return 0;
}
}
}
void Sort(long l,long r)
{
long i = l, j = r;
ntype x, y;
x = points[(l + r) / 2 - 1];
do {
while (cmp(&points[i-1], &x) == 1)
i++;
while (cmp(&x, &points[j-1]) == 1)
j--;
if (i <= j) {
y = points[i-1];
points[i-1] = points[j-1];
points[j-1] = y;
i++;
j--;
}
} while (i <= j);
if (l < j)
Sort(l, j);
if (i < r)
Sort(i, r);
}
int main(void)
{
long FORLIM, FORLIM1;
scanf("%ld%ld%ld%ld", &x, &y, &z, &p);
FORLIM = p;
for (i = 1; i <= FORLIM; i++) {
scanf("%ld%ld%ld", &a[i-1].x, &a[i-1].y, &a[i-1].z);
if (a[i-1].x == 0)
a[i-1].w = 0;
else if (a[i-1].y == 0)
a[i-1].w = 1;
else
a[i-1].w = 2;
}
FORLIM = p;
for (i = 1; i <= FORLIM; i++) {
FORLIM1 = p;
for (j = i + 1; j <= FORLIM1; j++) {
if (a[i-1].w != a[j-1].w) {
if (a[i-1].w != 0 && a[j-1].w != 0) {
if (a[i-1].x == a[j-1].x) {
h++;
points[h-1].x = a[i-1].x;
points[h-1].y = max(&a[i-1].y, &a[j-1].y);
points[h-1].z = max(&a[i-1].z, &a[j-1].z);
}
} else if (a[i-1].w != 1 && a[j-1].w != 1) {
if (a[i-1].y == a[j-1].y) {
h++;
points[h-1].y = a[i-1].y;
points[h-1].x = max(&a[i-1].x, &a[j-1].x);
points[h-1].z = max(&a[i-1].z, &a[j-1].z);
}
} else if (a[i-1].w != 2 && a[j-1].w != 2) {
if (a[i-1].z == a[j-1].z) {
h++;
points[h-1].z = a[i-1].z;
points[h-1].y = max(&a[i-1].y, &a[j-1].y);
points[h-1].x = max(&a[i-1].x, &a[j-1].x);
}
}
}
}
}
Sort(1L, h);
ans = x;
ans *= y * z;
FORLIM = p;
for (i = 1; i <= FORLIM; i++) {
if (a[i-1].w == 0)
ans -= x;
else if (a[i-1].w == 1)
ans -= y;
else if (a[i-1].w == 2)
ans -= z;
}
if (h != 0)
ans++;
FORLIM = h;
for (i = 2; i <= FORLIM; i++) {
if (points[h-1].x != points[h-2].x
|| points[h-1].y != points[h-2].y ||
points[h-1].z != points[h-2].z)
ans++;
else
ans += 0.5;
}
printf("%0.0f\n", ans);
return 0;
}
|
|
