Competitive Programming: CodeSignal – canScore (A World Cup Challenge)

/*
 * We're going to create a graph with each attacking player as a vertex.
 * 
 * For each pair of attacking players, we check each defensive player to
 * see if the defensive player is less than distance d from the line
 * segment between the attacking players. If no defensive player is close
 * enough to intercept a pass, we add an edge to the graph between the two
 * attacking players.
 * 
 * Finally, we do a depth-first search from vertex 0 (the goalkeeper) to
 * find whether a path exists to the best scorer.
 * 
 */
public class Main {

  static boolean[][] graph;
  static boolean[] marked;

  static boolean canScore(int[][] attackingPlayers,
      int[][] defendingPlayers, int d) {

    int apLen = attackingPlayers.length;
    int dpLen = defendingPlayers.length;

    graph = new boolean[apLen][apLen];

    // check each pair of players
    for (int i = 0; i < apLen - 1; i++) {
      PT a = new PT(attackingPlayers[i][0], attackingPlayers[i][1]);

      for (int j = i + 1; j < apLen; j++) {
        PT b = new PT(attackingPlayers[j][0], attackingPlayers[j][1]);

        boolean ok = true;

        // is a defender within distance d?
        for (int k = 0; k < dpLen; k++) {
          PT c = new PT(defendingPlayers[k][0], defendingPlayers[k][1]);

          if (Geometry.DistancePointSegment(a, b, c) < d) {
            ok = false;
            break;
          }
        }

        // if defenders are too far, add the edge
        if (ok) {
          graph[i][j] = true;
          graph[j][i] = true;
        }
      }
    }

    marked = new boolean[apLen];

    dfs(0);

    return marked[apLen - 1];
  }

  static void dfs(int v) {
    marked[v] = true;
    for (int w = 0; w < graph[v].length; w++) {
      if (graph[v][w] && !marked[w]) {
        dfs(w);
      }
    }
  }

  public static void main(String[] args) {

    // Test cases

    // false
//  int[][] attackingPlayers = {{0, 0}, {1, 2}, {3, 1}};
//  int[][] defendingPlayers = {{2, 1}};
//  int d = 1;

    // true
    int[][] attackingPlayers = {{0, 0}, {1, 2}, {3, 3}, {3, 1}};
    int[][] defendingPlayers = {{2, 1}};
    int d = 1;

    System.out.println(canScore(attackingPlayers, defendingPlayers, d));
  }
}

class Geometry {
  // Computational geometry functions

  static final double EPS = 1e-12;

  static double dot(PT p, PT q) {
    return p.x * q.x + p.y * q.y;
  }

  static double dist2(PT p, PT q) {
    return dot(p.subtract(q), p.subtract(q));
  }

  static PT ProjectPointSegment(PT a, PT b, PT c) {
    double r = dot(b.subtract(a), b.subtract(a));
    if (Math.abs(r) < EPS)
      return a;
    r = dot(c.subtract(a), b.subtract(a)) / r;
    if (r < 0)
      return a;
    if (r > 1)
      return b;
    return a.add(b.subtract(a).multiply(r));
  }

  static double DistancePointSegment(PT a, PT b, PT c) {
    return Math.sqrt(dist2(c, ProjectPointSegment(a, b, c)));
  }
}

class PT {
  double x, y;

  PT() {}

  PT(double x, double y) {
    this.x = x;
    this.y = y;
  }

  PT(PT p) {
    this.x = p.x;
    this.y = p.y;
    {
    }
  }

  PT add(final PT p) {
    return new PT(x + p.x, y + p.y);
  }

  PT subtract(final PT p) {
    return new PT(x - p.x, y - p.y);
  }

  PT multiply(double c) {
    return new PT(x * c, y * c);
  }

  PT divide(double c) {
    return new PT(x / c, y / c);
  }

  @Override
  public String toString() {
    return "(" + x + "," + y + ")";
  }

}