#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{
float x;
float y;
float z;
} vec3;
float
dot(vec3 a, vec3 b)
{
return a.x * b.x + a.y * b.y + a.z * b.z;
}
vec3
scale(float s, vec3 a)
{
vec3 r;
r.x = s * a.x;
r.y = s * a.y;
r.z = s * a.z;
return r;
}
vec3
add(vec3 a, vec3 b)
{
vec3 r;
r.x = a.x + b.x;
r.y = a.y + b.y;
r.z = a.z + b.z;
return r;
}
int
intersect(vec3 a, vec3 b, vec3 *normals, vec3 *points, int nnormals)
{
vec3 ab = add(b, scale(-1, a));
float tfirst = 0;
float tlast = 1;
int i;
for(i = 0; i < nnormals; i++)
{
float d = dot(normals[i], points[i]);
float denom = dot(normals[i], ab);
float dist = d - dot(normals[i], a);
float t = dist / denom;
if(denom > 0 && t > tfirst)
{
tfirst = t;
}
else if(denom < 0 && t < tlast)
{
tlast = t;
}
}
return tfirst < tlast ? 1 : 0;
}
const vec3 N = {0,-1,0};
const vec3 S = {0,1,0};
const vec3 W = {-1,0,0};
const vec3 E = {1,0,0};
const vec3 D = {0,0,-1};
int
main(void)
{
vec3 normals[5];
vec3 player;
vec3 *targets;
int i;
int j;
vec3 *buildings;
vec3 *b;
int nbuildings = 0;
int n;
int m;
char line[300];
normals[0] = N;
normals[1] = S;
normals[2] = W;
normals[3] = E;
normals[4] = D;
/*5 sides for each building*/
buildings
= calloc(n
* 5, sizeof(*buildings
)); b = buildings;
for(i = 0; i < n; i++)
{
char *z;
for(j
= 0; j
< n
&& (z
= strtok(j
? NULL
: line
, " \n")) != NULL
; j
++) {
vec3 bottom;
vec3 top;
if(z[0] == '0') continue;
nbuildings++;
bottom.x = j;
bottom.y = i;
bottom.z = 0;
top.x = j + 1;
top.y = i + 1;
b[0] = top;
b[1] = bottom;
b[2] = top;
b[3] = bottom;
b[4] = top;
b += 5;
}
}
targets
= calloc(m
, sizeof(*targets
)); for(i = 0; i < m; i++)
{
int hit = 1;
for(j = 0; j < nbuildings; j++)
{
b = &buildings[j * 5];
if(intersect(player, targets[i], normals, b, 5) == 1)
{
hit = 0;
break;
}
}
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgoKdHlwZWRlZiBzdHJ1Y3QKewogICAgZmxvYXQgeDsKICAgIGZsb2F0IHk7CiAgICBmbG9hdCB6Owp9IHZlYzM7CgpmbG9hdApkb3QodmVjMyBhLCB2ZWMzIGIpCnsKICAgIHJldHVybiBhLnggKiBiLnggKyBhLnkgKiBiLnkgKyBhLnogKiBiLno7Cn0KCnZlYzMKc2NhbGUoZmxvYXQgcywgdmVjMyBhKQp7CiAgICB2ZWMzIHI7CiAgICByLnggPSBzICogYS54OwogICAgci55ID0gcyAqIGEueTsKICAgIHIueiA9IHMgKiBhLno7CiAgICByZXR1cm4gcjsKfQoKdmVjMwphZGQodmVjMyBhLCB2ZWMzIGIpCnsKICAgIHZlYzMgcjsKICAgIHIueCA9IGEueCArIGIueDsKICAgIHIueSA9IGEueSArIGIueTsKICAgIHIueiA9IGEueiArIGIuejsKICAgIHJldHVybiByOwp9CgppbnQKaW50ZXJzZWN0KHZlYzMgYSwgdmVjMyBiLCB2ZWMzICpub3JtYWxzLCB2ZWMzICpwb2ludHMsIGludCBubm9ybWFscykKewogICAgdmVjMyBhYiA9IGFkZChiLCBzY2FsZSgtMSwgYSkpOwogICAgZmxvYXQgdGZpcnN0ID0gMDsKICAgIGZsb2F0IHRsYXN0ID0gMTsKICAgIGludCBpOwogICAgZm9yKGkgPSAwOyBpIDwgbm5vcm1hbHM7IGkrKykKICAgIHsKICAgICAgICBmbG9hdCBkID0gZG90KG5vcm1hbHNbaV0sIHBvaW50c1tpXSk7CiAgICAgICAgZmxvYXQgZGVub20gPSBkb3Qobm9ybWFsc1tpXSwgYWIpOwogICAgICAgIGZsb2F0IGRpc3QgPSBkIC0gZG90KG5vcm1hbHNbaV0sIGEpOwogICAgICAgIGZsb2F0IHQgPSBkaXN0IC8gZGVub207CiAgICAgICAgaWYoZGVub20gPiAwICYmIHQgPiB0Zmlyc3QpCiAgICAgICAgewogICAgICAgICAgICB0Zmlyc3QgPSB0OwogICAgICAgIH0KICAgICAgICBlbHNlIGlmKGRlbm9tIDwgMCAmJiB0IDwgdGxhc3QpCiAgICAgICAgewogICAgICAgICAgICB0bGFzdCA9IHQ7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIHRmaXJzdCA8IHRsYXN0ID8gMSA6IDA7Cn0KCmNvbnN0IHZlYzMgTiA9IHswLC0xLDB9Owpjb25zdCB2ZWMzIFMgPSB7MCwxLDB9Owpjb25zdCB2ZWMzIFcgPSB7LTEsMCwwfTsKY29uc3QgdmVjMyBFID0gezEsMCwwfTsKY29uc3QgdmVjMyBEID0gezAsMCwtMX07CgppbnQKbWFpbih2b2lkKQp7CiAgICB2ZWMzIG5vcm1hbHNbNV07CiAgICB2ZWMzIHBsYXllcjsKICAgIHZlYzMgKnRhcmdldHM7CiAgICBpbnQgaTsKICAgIGludCBqOwogICAgdmVjMyAqYnVpbGRpbmdzOwogICAgdmVjMyAqYjsKICAgIGludCBuYnVpbGRpbmdzID0gMDsKICAgIGludCBuOwogICAgaW50IG07CiAgICBjaGFyIGxpbmVbMzAwXTsKICAgIG5vcm1hbHNbMF0gPSBOOwogICAgbm9ybWFsc1sxXSA9IFM7CiAgICBub3JtYWxzWzJdID0gVzsKICAgIG5vcm1hbHNbM10gPSBFOwogICAgbm9ybWFsc1s0XSA9IEQ7CiAgICBmZ2V0cyhsaW5lLCAzMDAsIHN0ZGluKTsKICAgIG4gPSBhdG9pKGxpbmUpOwogICAgLyo1IHNpZGVzIGZvciBlYWNoIGJ1aWxkaW5nKi8KICAgIGJ1aWxkaW5ncyA9IGNhbGxvYyhuICogNSwgc2l6ZW9mKCpidWlsZGluZ3MpKTsKICAgIGIgPSBidWlsZGluZ3M7CiAgICBmb3IoaSA9IDA7IGkgPCBuOyBpKyspCiAgICB7CiAgICAgICAgY2hhciAqejsKICAgICAgICBmZ2V0cyhsaW5lLCAzMDAsIHN0ZGluKTsKICAgICAgICBmb3IoaiA9IDA7IGogPCBuICYmICh6ID0gc3RydG9rKGogPyBOVUxMIDogbGluZSwgIiBcbiIpKSAhPSBOVUxMOyBqKyspCiAgICAgICAgewogICAgICAgICAgICB2ZWMzIGJvdHRvbTsKICAgICAgICAgICAgdmVjMyB0b3A7CiAgICAgICAgICAgIGlmKHpbMF0gPT0gJzAnKSBjb250aW51ZTsKICAgICAgICAgICAgbmJ1aWxkaW5ncysrOwogICAgICAgICAgICBib3R0b20ueCA9IGo7CiAgICAgICAgICAgIGJvdHRvbS55ID0gaTsKICAgICAgICAgICAgYm90dG9tLnogPSAwOwogICAgICAgICAgICB0b3AueCA9IGogKyAxOwogICAgICAgICAgICB0b3AueSA9IGkgKyAxOwogICAgICAgICAgICB0b3AueiA9IGF0b2koeik7CiAgICAgICAgICAgIGJbMF0gPSB0b3A7CiAgICAgICAgICAgIGJbMV0gPSBib3R0b207CiAgICAgICAgICAgIGJbMl0gPSB0b3A7CiAgICAgICAgICAgIGJbM10gPSBib3R0b207CiAgICAgICAgICAgIGJbNF0gPSB0b3A7CiAgICAgICAgICAgIGIgKz0gNTsKICAgICAgICB9CiAgICB9CiAgICBmZ2V0cyhsaW5lLCAzMDAsIHN0ZGluKTsKICAgIHBsYXllci54ID0gYXRvZihzdHJ0b2sobGluZSwgIiAiKSk7CiAgICBwbGF5ZXIueSA9IGF0b2Yoc3RydG9rKE5VTEwsICIgIikpOwogICAgcGxheWVyLnogPSBhdG9mKHN0cnRvayhOVUxMLCAiIFxuIikpOwogICAgZmdldHMobGluZSwgMzAwLCBzdGRpbik7CiAgICBtID0gYXRvaShsaW5lKTsKICAgIHRhcmdldHMgPSBjYWxsb2MobSwgc2l6ZW9mKCp0YXJnZXRzKSk7CiAgICBmb3IoaSA9IDA7IGkgPCBtOyBpKyspCiAgICB7CiAgICAgICAgaW50IGhpdCA9IDE7CiAgICAgICAgZmdldHMobGluZSwgMzAwLCBzdGRpbik7CiAgICAgICAgdGFyZ2V0c1tpXS54ID0gYXRvZihzdHJ0b2sobGluZSwgIiAiKSk7CiAgICAgICAgdGFyZ2V0c1tpXS55ID0gYXRvZihzdHJ0b2soTlVMTCwgIiAiKSk7CiAgICAgICAgdGFyZ2V0c1tpXS56ID0gYXRvZihzdHJ0b2soTlVMTCwgIiBcbiIpKTsKICAgICAgICBmb3IoaiA9IDA7IGogPCBuYnVpbGRpbmdzOyBqKyspCiAgICAgICAgewogICAgICAgICAgICBiID0gJmJ1aWxkaW5nc1tqICogNV07CiAgICAgICAgICAgIGlmKGludGVyc2VjdChwbGF5ZXIsIHRhcmdldHNbaV0sIG5vcm1hbHMsIGIsIDUpID09IDEpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGhpdCA9IDA7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBwcmludGYoIiVkXG4iLCBoaXQgPyAxIDogLTEpOwogICAgfQogICAgZnJlZShidWlsZGluZ3MpOwogICAgZnJlZSh0YXJnZXRzKTsKICAgIHJldHVybiAwOwp9