SRM528 Div2 Hard

1000

class Mosquitoes {
public:
  int getMaximum(vector <int> xs_, vector <int> v_, int R_) 
  {
    vector<double> xs, v;
    for (int i = 0; i < xs_.size(); ++i) xs.push_back(xs_[i]);
    for (int i = 0; i < v_.size(); ++i) v.push_back(v_[i]);
    double R = R_;

    const int size = xs.size();
    
    int mx = min(1, size);

    for (int i = 0; i < size; ++i) {
      for (int j = 0; j < size; ++j) {
        if (i == j) continue;

        int cnt = 0;
        double t = ((2.0 * R) - (xs[j] - xs[i])) / (v[j] - v[i]);
        double a = xs[i] + v[i] * t - 1e-7;
        double b = xs[j] + v[j] * t + 1e-7;

        if (t < 0.0) continue;
        for (int k = 0; k < size; ++k) {
          double c = xs[k] + v[k] * t;
          if (k == i || k == j) ++cnt;
          else if (a <= c && c <= b) ++cnt;
        }
        mx = max(mx, cnt);
      }
    }

    return mx;
  }

};