Einführung

Die Arena ist ein Flachland mit Wolkenkratzern, die Ihre Feinde als Deckung nutzen. Sie und Ihre Feinde schießen sich gegenseitig mit Lasern. Sie tragen alle Jet-Packs, die den Flug ermöglichen.

Welche Feinde kannst du mit deinem Laser treffen und welche verstecken sich?

Problem

Zunächst wird die Größe einer Arena durch eine ganze Zahl nin einer einzelnen Zeile angegeben. Die folgenden nZeilen enthalten nganze Zahlen pro Zeile, die durch ein Leerzeichen getrennt sind. Jede Ganzzahl repräsentiert die Höhe des Gebäudes an dieser Stelle. Jedes Gebäude ist ein rechteckiger Körper, 1 Einheit mal 1 Einheit mal Höheneinheit.

Als nächstes wird Ihr Standort auf einer einzige Zeile als drei Gleitkommazahlen gegeben x, y, z.

Schließlich wird die Anzahl der Feinde durch eine ganze Zahl min einer einzelnen Zeile angegeben. Die folgenden mZeilen enthalten drei Gleitkommazahlen pro Zeile, die durch ein Leerzeichen getrennt sind. Diese stellen die x, yund zKoordinaten eines Feindes. Das Koordinatensystem ist wie folgt definiert:

• x wird in der Stadteingabe von links nach rechts gemessen
• y wird von oben nach unten gemessen
• z wird von Grund auf gemessen

Wenn für jeden Feind eine freie Linie von Ihnen zu diesem Feind gezogen werden kann, geben Sie eine positive ganze Zahl aus. Andernfalls geben Sie eine negative Ganzzahl aus. Ausgänge durch eine neue Zeile trennen.

Sample Input

Mit '#' gekennzeichnete Kommentare helfen Ihnen dabei, schnell zu erkennen, was die einzelnen Zeilen bewirken. Sie sind in der tatsächlichen Eingabe nicht vorhanden.

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

Beispielausgabe

Für die obige Beispieleingabe geben wir Folgendes aus:

-1
1
1

Annahmen

• 0 n<<100
• 0 m<<100
• 0 <= x<=n
• 0 <= y<=n
• 0 <= z<n
• Die Spieler werden sich nicht an oder innerhalb einer Ecke, Kante oder Seite eines Gebäudes befinden
• Ihre Sichtlinie auf einen Feind wird niemals die Ecke, den Rand oder die Seite eines Gebäudes berühren
• Ein Spieler ist kein Hindernis

Perl, 301 296 282

Edit 2: Eigentlich, Konkurrenz oder nicht, gibt es keinen Grund, nicht ein bisschen weiter zu golfen. Testen Sie es online .

Bearbeiten: Ein paar Klammern weg, einfacher Regex für ungleich Null Ganzzahl zu überprüfen.

Mit Zeilenumbrüchen und Einrückung zur besseren Lesbarkeit:

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<>

Es erfordert 5.14wegen des skalaren (Array-Referenz) Arguments zu pop.

Python 2.7 - 429 420 308 308 Zeichen

Ich dachte, diese Herausforderung sei eher ein mathematisches Problem als ein Code-Golf-Problem. Seien Sie also nicht zu hart für mich, wenn ich einige offensichtliche Optimierungen übersehen hätte. Sowieso ist hier der 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)

Dies sollte für Rand- und Eckfälle funktionieren (Wortspiel unbeabsichtigt) und ist ziemlich solide. Ergebnis für das Beispiel:

-1
1
1

Und hier ist eine "kurze" Erklärung:

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

Ich denke, das ist voller Mängel. Übrigens habe ich beim Verschachteln Zeichen gespeichert (erste Ebene ist ein Leerzeichen, zweite ein Tab, dann ein Tab und ein Leerzeichen ...). Ich hoffe, nach all dieser Antwort kann der Weg weisen, um es zu tun.

C - 2468

Überhaupt nicht golfen, aber hoffentlich ist es ein Ausgangspunkt für interessantere Implementierungen. Die Umsetzung von intersectwird stark von Adrian Boeing beschnitten . Sein Pseudocode war unvollständig, aber seine Erklärung der Mathematik war von unschätzbarem Wert. Die Grundidee ist, dass Sie eine Linie vom Spieler zum Ziel nehmen und diese an alle Wände jedes Gebäudes kleben und die Länge für jede Wand aktualisieren. Die verbleibende Länge ist der Teil innerhalb des Gebäudes. Wenn er also Null ist, gab es keinen Schnittpunkt.

#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;
}