제출 #930222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930222		NeroZein	Izvanzemaljci (COI21_izvanzemaljci)	C++17	5 / 100	19 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);
}

bool intersect(int mxx, int mxy, int len, int mnx2, int mny2) {
  return mxx + len < mnx2 && mxy + len < mny2; 
}

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 len1 = max({1, mxx - mnx, mxy - mny});
    long long val = (long long) len1 * len1;
    int len2 = max({1, smxx[i] - smnx[i], smxy[i] - smny[i]});
    val += (long long) len2 * len2;
    if (!intersect(mxx, mxy, len1, smnx[i], smny[i]) && val < ret) {
      ret = val;
      vec.clear();
      vec.push_back({mnx, mny, len1});
      vec.push_back({smnx[i], smny[i], len2});
    }
    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 len1 = max({1, mxx - mnx, mxy - mny});
    long long val = (long long) len1 * len1;
    int len2 = max({1, smxx[i] - smnx[i], smxy[i] - smny[i]});
    val += (long long) len2 * len2;
    if (!intersect(mxx, mxy, len1, smnx[i], smny[i]) && val < ret) {
      ret = val;
      vec.clear();
      vec.push_back({mnx, mny, len1});
      vec.push_back({smnx[i], smny[i], len2});
    }
    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;
  }
  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);
  if (k == 1) {
    cout << mnX << ' ' << mnY << ' ' << max({1, mxX - mnX, mxY - mnY}) << '\n';
    return 0; 
  }
  int len = max({1, mxX - mxX, mxY - mnY});
  long long cur = (long long) len * len + 1; 
  auto [res, vec] = solve(p);
  assert(!vec.empty());
  if (res < cur) {
    for (auto& it : vec) {
      cout << it[0] << ' ' << it[1] << ' ' << it[2] << '\n';
    }     
  } else {
    cout << mnX << ' ' << mnY << ' ' << max({1, mxX - mnX, mxY - mnY}) << '\n';
    cout << mxX + 1 << ' ' << mxY + 1 << ' ' << 1 << '\n';
  }
  return 0;
}

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