introduction

L'arène est une plaine parsemée de gratte-ciel, que vos ennemis utilisent pour se couvrir. Vous et vos ennemis vous tirez dessus avec des lasers. Vous transportez tous des jet packs, permettant le vol.

Quels ennemis pouvez-vous frapper avec votre laser et lesquels se cachent?

Problème

Tout d'abord, la taille d'une arène est donnée par un entier nsur une seule ligne. Les nlignes suivantes contiennent des nentiers par ligne séparés par un espace. Chaque entier représente la hauteur du bâtiment à cet endroit. Chaque bâtiment est un solide rectangulaire de 1 unité par 1 unité de hauteur.

Ensuite, votre position est donnée sur une seule ligne en trois nombres à virgule flottante x, y, z.

Enfin, le nombre d'ennemis est donné par un entier msur une seule ligne. Les mlignes suivantes contiennent trois nombres à virgule flottante par ligne séparés par un espace. Ceux-ci représentent le x, yet les zcoordonnées d'un ennemi. Le système de coordonnées est défini comme suit:

• x est mesurée de gauche à droite dans l'entrée ville
• y est mesuré de haut en bas
• z est mesuré à partir de zéro

Pour chaque ennemi, si une ligne dégagée peut être tracée de vous vers cet ennemi, émettez un entier positif . Sinon, sortez un entier négatif . Sorties séparées avec une nouvelle ligne.

Exemple d'entrée

Les commentaires, notés «#», sont présents pour vous aider à voir rapidement ce que fait chaque ligne. Ils ne seront pas présents dans l'entrée réelle.

5              # Size of the map
0 0 0 0 0      # Buildings
0 0 0 0 0      # Buildings
4 4 4 4 4      # Buildings
0 0 0 0 0      # Buildings
0 0 0 0 0      # Buildings
2.5 0.0 4.0    # Your location
3              # Number of enemies
2.5 5.0 0.1    # Enemy location
2.5 5.0 5.0    # Enemy location
0.0 2.7 4.5    # Enemy location

Exemple de sortie

Pour l'exemple d'entrée ci-dessus, nous générons les éléments suivants:

-1
1
1

Hypothèses

• 0 n<<100
• 0 m<<100
• 0 <= x<=n
• 0 <= y<=n
• 0 <= z<n
• Les joueurs ne seront pas situés sur ou à l'intérieur d'un coin, d'un bord ou d'un côté d'un bâtiment
• Votre ligne de vue vers un ennemi ne sera jamais tangente au coin, au bord ou au côté d'un bâtiment
• Un joueur n'est pas une obstruction

Perl, 301 296 282

Edit 2: En fait, en compétition ou non, il n'y a aucune raison de ne pas le jouer un peu plus loin. Testez-le en ligne .

Edit: couple de parenthèses disparu, regex plus simple pour vérifier un entier non nul.

Avec des nouvelles lignes et un retrait pour la lisibilité:

sub i{<>=~/\S+/g}
@b=map[i],@r=0..<>-1;
print.1<=>(map{
    @a[1,0,2,4,3]=@a;
    @b=map{$i=$_;[map$b[$_][$i],@r]}@r;
    grep$a[3]
        &&($k=(($x=$_)-$a[0])/$a[3])**2<=$k
        &&pop[sort map@{$b[$_]}[$x-!!$x,$x],
                   ($_=$a[1]+$k*$a[4]),$_-/^\d+$/]
           >=$a[2]+$k*$a[5]
    ,@R=@r
}@a=map$_-shift@v,i,@u=@v=@$_),$/for([i])x<>

Il nécessite en 5.14raison de l'argument scalaire (référence de tableau) à pop.

Python 2.7 - 429 420 308 308 caractères

J'ai pensé à ce défi plus comme un problème mathématique qu'un problème de golf de code, alors ne soyez pas trop dur avec moi si j'ai raté des optimisations évidentes. Quoi qu'il en soit, voici le code:

b=lambda:raw_input().split()
m=map
d=range(input())
h=[m(int,b())for _ in d]
x,y,z=m(float,b())
for e,f,g in[m(float,b())for _ in[1]*input()]:o=lambda x,y,u,v,i,j:i<=x+u/v*(j+1-y)<=i+1<[]>z+(g-z)/v*(j+1-y)<=max(h[i][j:j+2])if v else 0;print 1-2*any(o(x,y,e-x,f-y,j,i)+o(y,x,f-y,e-x,i,j)for j in d for i in d)

Cela devrait fonctionner pour les cas de bord et d'angle (jeu de mots involontaire) et est assez solide. Sortie pour l'exemple fourni:

-1
1
1

Et voici une "courte" explication:

fast_read = lambda : raw_input().split() # define a helper
# m = map another helper
grid_range = range(input())
houses = [map(int, fast_read()) for _ in grid_range]
# 'map(int,...)' is a shorter version of '[int(a) for a in ...]'
pos_x,pos_y,pos_z = map(float, fast_read()) # read the player position
# the following loops through all enemy coordinates
for ene_x, ene_y, ene_z in [map(float,fast_read()) for _ in[1]*input()]:
    vec_z = ene_z - pos_z
    # is_hit macro uses vector math to detemine whether we hit a specific wall
    # wallhit -> 1
    # no wallhit -> 0
    is_hit = lambda pos_x, pos_y, vec_x, vec_y, co_x, co_y:\
        (co_x <= pos_x + vec_x/vec_y * (co_y + 1 - pos_y) <= co_x + 1 # check if hit_x is good
        < [] > # an effective and
        pos_z + (ene_z - pos_z)/vec_y * (co_y + 1 - pos_y) <= max(houses[co_x][co_y:co_y + 2]) # check if hit_z is good
        if vec_y else 0) # if vec_y is 0 we can't hit the wall parallel to y
    print (.5 - # can hit -> 0.5 - 0 = 0.5, hit -> 0.5 - 1 = -0.5
            any( # if we hit any wall
                # we swap x and y-coordinate because we read them "incorrect"
                is_hit(pos_x, pos_y, ene_x-pos_x, ene_y-pos_y, cur_y, cur_x) # check for hit in x-direction
                + # effective 'or'
                is_hit(pos_y, pos_x, ene_y-pos_y, ene_x-pos_x, cur_x, cur_y) # check for hit in y-direction
                    for cur_y in grid_range # loop y
                for cur_x in grid_range)) # loop x

Je suppose que c'est plein de défauts. Btw J'ai enregistré des caractères lors de l'imbrication (le premier niveau est un espace, le deuxième un onglet, puis un onglet et un espace ...). J'espère qu'après tout, cette réponse pourra montrer la voie à suivre.

C - 2468

Pas du tout joué au golf, mais j'espère que c'est un point de départ pour des implémentations plus intéressantes. La mise en œuvre de intersectest lourdement gérée par Adrian Boeing . Son pseudo-code était incomplet, mais son explication des mathématiques était inestimable. L'idée de base est que vous prenez une ligne du joueur vers la cible et que vous l'attachez à tous les murs de chaque bâtiment, en mettant à jour la longueur de chaque mur. La longueur restante est la partie à l'intérieur du bâtiment, donc si elle est nulle, il n'y avait pas d'intersection.

#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;
    fgets(line, 300, stdin);
    n = atoi(line);
    /*5 sides for each building*/
    buildings = calloc(n * n * 5, sizeof(*buildings));
    b = buildings;
    for(i = 0; i < n; i++)
    {
        char *z;
        fgets(line, 300, stdin);
        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;
            top.z = atoi(z);
            b[0] = top;
            b[1] = bottom;
            b[2] = top;
            b[3] = bottom;
            b[4] = top;
            b += 5;
        }
    }
    fgets(line, 300, stdin);
    player.x = atof(strtok(line, " "));
    player.y = atof(strtok(NULL, " "));
    player.z = atof(strtok(NULL, " \n"));
    fgets(line, 300, stdin);
    m = atoi(line);
    targets = calloc(m, sizeof(*targets));
    for(i = 0; i < m; i++)
    {
        int hit = 1;
        fgets(line, 300, stdin);
        targets[i].x = atof(strtok(line, " "));
        targets[i].y = atof(strtok(NULL, " "));
        targets[i].z = atof(strtok(NULL, " \n"));
        for(j = 0; j < nbuildings; j++)
        {
            b = &buildings[j * 5];
            if(intersect(player, targets[i], normals, b, 5) == 1)
            {
                hit = 0;
                break;
            }
        }
        printf("%d\n", hit ? 1 : -1);
    }
    free(buildings);
    free(targets);
    return 0;
}