cafelier@SRM

SRM445 275

あとで | 11:53 |

0.5刻みで全部試すコード。

class TheNewHouseDivOne { public:
  double distance(vector <int> x, vector <int> y, int k) 
  {
    double minD = 1e+99;
    for(double X=-50; X<=+50; X+=0.5)
      for(double Y=-50; Y<=+50; Y+=0.5)
      {
        vector<double> d;
        for(int i=0; i<x.size(); ++i)
          d.push_back( abs(x[i]-X) + abs(y[i]-Y) );
        nth_element(d.begin(), d.begin()+k-1, d.end());
        minD = min(minD, d[k-1]);
      }
    return minD;
  }
};

• マンハッタン距離なので中線は全て45度線、しかも格子点を通る
• なので交点は必ず0.5刻み座標に全て乗る

というところか。なるほどなー。