SRM528 Div2 Hard

1000

view plainprint?

1. class Mosquitoes {  
2. public:  
3.   int getMaximum(vector <int> xs_, vector <int> v_, int R_)   
4.   {  
5.     vector<double> xs, v;  
6.     for (int i = 0; i < xs_.size(); ++i) xs.push_back(xs_[i]);  
7.     for (int i = 0; i < v_.size(); ++i) v.push_back(v_[i]);  
8.     double R = R_;  
9.   
10.     const int size = xs.size();  
11.       
12.     int mx = min(1, size);  
13.   
14.     for (int i = 0; i < size; ++i) {  
15.       for (int j = 0; j < size; ++j) {  
16.         if (i == j) continue;  
17.   
18.         int cnt = 0;  
19.         double t = ((2.0 * R) - (xs[j] - xs[i])) / (v[j] - v[i]);  
20.         double a = xs[i] + v[i] * t - 1e-7;  
21.         double b = xs[j] + v[j] * t + 1e-7;  
22.   
23.         if (t < 0.0) continue;  
24.         for (int k = 0; k < size; ++k) {  
25.           double c = xs[k] + v[k] * t;  
26.           if (k == i || k == j) ++cnt;  
27.           else if (a <= c && c <= b) ++cnt;  
28.         }  
29.         mx = max(mx, cnt);  
30.       }  
31.     }  
32.   
33.     return mx;  
34.   }  
35.   
36. };  

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

};