Submission #930221

#	Time	Username	Problem	Language	Result	Execution time	Memory
930221		NeroZein	Izvanzemaljci (COI21_izvanzemaljci)	C++17	5 / 100	18 ms	1116 KiB

izvanzemaljci

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

struct point {
  int x, y;
};

void print(point p) {
  debug(p.x, p.y);
}

pair<long long, vector<array<int, 3>>> solve(vector<point>& p) {// k = 2
  sort(p.begin(), p.end(), [&](point i, point j) {
    return i.x < j.x;
  });
  vector<array<int, 3>> vec;
  long long ret = LLONG_MAX / 3;
  int n = p.size(); 
  vector<int> smnx(n), smny(n);
  vector<int> smxx(n), smxy(n);
  smnx[n - 1] = smxx[n - 1] = p[n - 1].x;
  smny[n - 1] = smxy[n - 1] = p[n - 1].y;
  for (int i = n - 2; i >= 0; --i) {
    smnx[i] = min(p[i].x, smnx[i + 1]);
    smxx[i] = max(p[i].x, smxx[i + 1]);
    smny[i] = min(p[i].y, smny[i + 1]);
    smxy[i] = max(p[i].y, smxy[i + 1]);
  }
  int mnx = p[0].x, mny = p[0].y;
  int mxx = p[0].x, mxy = p[0].y;
  for (int i = 1; i < n; ++i) {
    int mx = max({1, mxx - mnx, mxy - mny});
    long long val = (long long) mx * mx;
    mx = max({1, smxx[i] - smnx[i], smxy[i] - smny[i]});
    val += (long long) mx * mx;
    if (val < ret) {
      ret = val;
      vec.clear();
      vec.push_back({mnx, mny, max({1, mxx - mnx, mxy - mny})});
      vec.push_back({smnx[i], smny[i], max({1, smxx[i] - smnx[i], smxy[i] - smny[i]})});
    }
    mnx = min(mnx, p[i].x);
    mxx = max(mxx, p[i].x);
    mny = min(mny, p[i].y);
    mxy = max(mxy, p[i].y);
  }
  sort(p.begin(), p.end(), [&](point i, point j) {
    return i.x < j.x;
  });
  smnx[n - 1] = smxx[n - 1] = p[n - 1].x;
  smny[n - 1] = smxy[n - 1] = p[n - 1].y;
  for (int i = n - 2; i >= 0; --i) {
    smnx[i] = min(p[i].x, smnx[i + 1]);
    smxx[i] = max(p[i].x, smxx[i + 1]);
    smny[i] = min(p[i].y, smny[i + 1]);
    smxy[i] = max(p[i].y, smxy[i + 1]);
  }
  mnx = p[0].x, mny = p[0].y;
  mxx = p[0].x, mxy = p[0].y;
  for (int i = 1; i < n; ++i) {
    int mx = max({1, mxx - mnx, mxy - mny});
    long long val = (long long) mx * mx;
    mx = max({1, smxx[i] - smnx[i], smxy[i] - smny[i]});
    val += (long long) mx * mx;
    if (val < ret) {
      ret = val;
      vec.clear();
      vec.push_back({mnx, mny, max({1, mxx - mnx, mxy - mny})});
      vec.push_back({smnx[i], smny[i], max({1, smxx[i] - smnx[i], smxy[i] - smny[i]})});
    }
    mnx = min(mnx, p[i].x);
    mxx = max(mxx, p[i].x);
    mny = min(mny, p[i].y);
    mxy = max(mxy, p[i].y);
  }
  return {ret, vec};
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  vector<point> p(n);
  for (int i = 0; i < n; ++i) {
    cin >> p[i].x >> p[i].y;
  }
  if (k == 1) {
    int mnX = p[0].x, mxX = p[0].x;
    int mnY = p[0].y, mxY = p[0].y;
    for (int i = 1; i < n; ++i) {
      mnX = min(mnX, p[i].x);
      mxX = max(mxX, p[i].x);
      mnY = min(mnY, p[i].y);
      mxY = max(mxY, p[i].y);
    }
    assert(mxX >= mnX && mxY >= mnY);
    cout << mnX << ' ' << mnY << ' ' << max({1, mxX - mnX, mxY - mnY}) << '\n';
    return 0; 
  }
  vector<array<int, 3>> vec = solve(p).second; 
  assert(!vec.empty());
  for (auto& it : vec) {
    cout << it[0] << ' ' << it[1] << ' ' << it[2] << '\n';
  }
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 21
• Subtask 3: 0 / 12
• Subtask 4: 0 / 30
• Subtask 5: 0 / 32