CS Academy Round #34 Point in Kgon

復習

問題

https://csacademy.com/contest/round-34/task/point-in-kgon/

コード

import java.util.Scanner;

public class Main {

  private static final int MOD = (int) (1e9 + 7);

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    int N = in.nextInt();
    int K = in.nextInt();
    long[] x = new long[N * 2];
    long[] y = new long[N * 2];
    for (int i = 0; i < N; i++) {
      x[i] = in.nextInt();
      y[i] = in.nextInt();
    }
    int px = in.nextInt();
    int py = in.nextInt();
    for (int i = 0; i < N; i++) {
      x[i] -= px;
      y[i] -= py;
      x[i + N] = x[i];
      y[i + N] = y[i];
    }

    Combination combination = new Combination(N, MOD);
    long sum = 0;
    int bottom = 0;
    for (int i = 0; i < N; i++) {
      while (bottom + 1 < N * 2 && x[i] * y[bottom + 1] - y[i] * x[bottom + 1] >= 0) {
        bottom++;
      }

      int count = bottom - i;
      sum += combination.get(count, K - 1);
      sum %= MOD;
    }

    long ans = (combination.get(N, K) - sum + MOD) % MOD;
    System.out.println(ans);
  }

  static class Combination {

    private long[] fact;
    private long[] invFact;
    private int MOD;

    public Combination(int max, int MOD) {
      this.MOD = MOD;
      long[] inv = new long[max + 1];
      fact = new long[max + 1];
      invFact = new long[max + 1];
      inv[1] = 1;
      for (int i = 2; i <= max; i++) {
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
      }
      fact[0] = invFact[0] = 1;
      for (int i = 1; i <= max; i++) {
        fact[i] = fact[i - 1] * i % MOD;
      }
      for (int i = 1; i <= max; i++) {
        invFact[i] = invFact[i - 1] * inv[i] % MOD;
      }
    }

    public long get(int x, int y) {
      if (x < y) {
        return 0;
      }
      return fact[x] * invFact[y] % MOD * invFact[x - y] % MOD;
    }
  }
}