leetcode-go/written-exam/kickstart-2019-E/no2/main.cc

#include <cstdio>
#include <cstring>

#define D_MAX 100000
#define S_MAX 100000

char ans[D_MAX + 1];
int C[S_MAX];
int E[S_MAX];

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

struct Frac {
  int a;
  int b;

  bool operator==(const Frac &that) const { 
    return this->a == that.a && this->b == that.b;
  }

  void Norm() {
    int c = gcd(a, b);
    a /= c;
    b /= c;
  }
} frac;

int main() {
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int D, S, C_sum = 0, E_sum = 0;
    scanf("%d %d", &D, &S);
    bool parallel = true;
    for (int i = 0; i < S; i++) {
      scanf("%d %d", &C[i], &E[i]);
      C_sum += C[i];
      E_sum += E[i];
      if (i == 0) {
        frac = Frac{C[i], E[i]};
        frac.Norm();
        continue;
      }
      Frac curr = Frac{C[i], E[i]};
      curr.Norm();
      parallel |= frac == curr;
    }
    memset(ans, 0, sizeof(ans));
    for (int i = 0, A, B; i < D; i++) {
      scanf("%d %d", &A, &B);
      if (C_sum < A || E_sum < B) {
        ans[i] = 'N';
        continue;
      }
      if (parallel) {
        if (A * frac.b > (E_sum - B) * frac.a) ans[i] = 'N';
        else ans[i] = 'Y';
        continue;
      }
      int a = C[0] * (E_sum - B) - E[0] * A;
      int b = C[0] * E[1] - C[1] * E[0];
      Frac y = Frac{a, b};
      y.Norm();
      a = y.a;
      b = y.b;
      Frac x = Frac{A * b - C[1] * a, C[0] * b};
      x.Norm();
      if (y.a * y.b >= 0 && x.a * x.b >= 0 && y.a <= y.b && x.a <= x.b) {
        ans[i] = 'Y';
        continue;
      }
      Frac x0 = Frac{A, C[0]};
      x0.Norm();
      Frac x1 = Frac{E_sum - B, E[0]};
      x1.Norm();
      if (x0.a * x1.b > x0.b * x1.a) {
        if (x0.a > x0.b) ans[i] = 'Y';
        else ans[i] = 'N';
      } else {
        ans[i] = 'Y';
      }
    }
    printf("Case #%d: %s\n", t, ans);
  }
  return 0;
}