// [NWERC'14] Gathering, by Jan Kuipers #include #include #include #include using namespace std; int N; vector get_distances(vector& x) { vector dist(N); for (int i=0; i& x, vector& dist) { if (X > x.back()) { return dist.back() + x.size() * (X - x.back()); } int i = lower_bound(x.begin(), x.end(), X) - x.begin(); return dist[i] + (X-x[i]) * (2*i-N); } void add_off_by_one(vector& posx, vector& posy, long long x, long long y) { posx.push_back(x); posy.push_back(y); posx.push_back(x+1); posy.push_back(y); posx.push_back(x); posy.push_back(y+1); posx.push_back(x+1); posy.push_back(y+1); } int main() { cin >> N; vector x(N), y(N); for (int i=0; i> x[i] >> y[i]; } long long D; cin >> D; long long mind1 = -LONG_LONG_MAX, maxd1 = LONG_LONG_MAX; long long mind2 = -LONG_LONG_MAX, maxd2 = LONG_LONG_MAX; for (int i=0; imaxd1 || mind2>maxd2) { cout << "impossible" << endl; return 0; } sort(x.begin(), x.end()); sort(y.begin(), y.end()); vector x_distance = get_distances(x); vector y_distance = get_distances(y); long long X=x[N/2], Y=y[N/2]; long long d1=X+Y, d2=X-Y; if (d1>=mind1 && d1<=maxd1 && d2>=mind2 && d2<=maxd2) { cout << (get_distance(X, x, x_distance) + get_distance(Y, y, y_distance)) << endl; return 0; } vector posx, posy; for (int i=0; i=mind1 && d1<=maxd1 && d2>=mind2 && d2<=maxd2) { long long distance = get_distance(posx[i], x, x_distance) + get_distance(posy[i], y, y_distance); result = min(result, distance); } } cout << result << endl; return 0; }