Submission #693923

#TimeUsernameProblemLanguageResultExecution timeMemory
69392379brueIzvanzemaljci (COI21_izvanzemaljci)C++17
26 / 100
64 ms11724 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, k; void solve1(); void solve2(); int main(){ scanf("%d %d", &n, &k); if(n==1){ ll x, y; scanf("%lld %lld", &x, &y); for(int i=0; i<k; i++) printf("%lld %lld 1\n", x+i+i, y+i+i); return 0; } if(k==1) solve1(); else if(k==2) solve2(); } void solve1(){ ll xMin = 1e9, xMax = -1e9, yMin = 1e9, yMax = -1e9; for(int i=1; i<=n; i++){ ll x, y; scanf("%lld %lld", &x, &y); xMin = min(x, xMin), yMin = min(y, yMin); xMax = max(x, xMax), yMax = max(y, yMax); } printf("%lld %lld %lld", xMin, yMin, max(xMax - xMin, yMax - yMin)); } void solve2(){ vector<pair<ll, ll> > points (n); vector<ll> x(n), y(n); vector<ll> xMin1(n, 1e9), xMax1(n, -1e9), yMin1(n, 1e9), yMax1(n, -1e9); vector<ll> xMin2(n, 1e9), xMax2(n, -1e9), yMin2(n, 1e9), yMax2(n, -1e9); for(int i=0; i<n; i++) scanf("%lld %lld", &points[i].first, &points[i].second); sort(points.begin(), points.end()); /// 가로로 찾기 for(int i=0; i<n; i++){ xMin1[i] = xMax1[i] = xMin2[i] = xMax2[i] = x[i] = points[i].first; yMin1[i] = yMax1[i] = yMin2[i] = yMax2[i] = y[i] = points[i].second; } for(int i=1; i<n; i++){ xMin1[i] = min(xMin1[i], xMin1[i-1]); xMax1[i] = max(xMax1[i], xMax1[i-1]); yMin1[i] = min(yMin1[i], yMin1[i-1]); yMax1[i] = max(yMax1[i], yMax1[i-1]); } for(int i=n-2; i>=0; i--){ xMin2[i] = min(xMin2[i], xMin2[i+1]); xMax2[i] = max(xMax2[i], xMax2[i+1]); yMin2[i] = min(yMin2[i], yMin2[i+1]); yMax2[i] = max(yMax2[i], yMax2[i+1]); } ll justone = max({1LL, xMax1[n-1] - xMin1[n-1], yMax1[n-1] - yMin1[n-1]}); /// 전체 하나로 할 경우의 답 ll ans = INT_MAX; int ansIdx = -1, ansMode = -1; for(int i=0; i<n-1; i++){ /// i 기준 정렬 if(x[i] == x[i+1]) continue; ll tmp = max({1LL, xMax1[i] - xMin1[i], yMax1[i] - yMin1[i], xMax2[i+1] - xMin2[i+1], yMax2[i+1] - yMin2[i+1]}); if(ans > tmp) ans = tmp, ansIdx = i, ansMode = 0; } /// 세로로 찾기 sort(points.begin(), points.end(), [&](auto &a, auto &b){ return a.second < b.second; }); /// 가로로 찾기 for(int i=0; i<n; i++){ xMin1[i] = xMax1[i] = xMin2[i] = xMax2[i] = x[i] = points[i].first; yMin1[i] = yMax1[i] = yMin2[i] = yMax2[i] = y[i] = points[i].second; } for(int i=1; i<n; i++){ xMin1[i] = min(xMin1[i], xMin1[i-1]); xMax1[i] = max(xMax1[i], xMax1[i-1]); yMin1[i] = min(yMin1[i], yMin1[i-1]); yMax1[i] = max(yMax1[i], yMax1[i-1]); } for(int i=n-2; i>=0; i--){ xMin2[i] = min(xMin2[i], xMin2[i+1]); xMax2[i] = max(xMax2[i], xMax2[i+1]); yMin2[i] = min(yMin2[i], yMin2[i+1]); yMax2[i] = max(yMax2[i], yMax2[i+1]); } for(int i=0; i<n-1; i++){ /// i 기준 정렬 if(y[i] == y[i+1]) continue; ll tmp = max({1LL, xMax1[i] - xMin1[i], yMax1[i] - yMin1[i], xMax2[i+1] - xMin2[i+1], yMax2[i+1] - yMin2[i+1]}); if(ans > tmp) ans = tmp, ansIdx = i, ansMode = 1; } /// 답 출력하기 if(justone <= ans || ansMode == -1){ printf("%lld %lld %lld\n", xMin1[n-1], yMin1[n-1], justone); printf("%lld %lld %lld\n", 2'000'000'000LL, 2'000'000'000LL, justone); } else if(ansMode == 0){ sort(points.begin(), points.end()); /// 가로로 찾기 for(int i=0; i<n; i++){ xMin1[i] = xMax1[i] = xMin2[i] = xMax2[i] = x[i] = points[i].first; yMin1[i] = yMax1[i] = yMin2[i] = yMax2[i] = y[i] = points[i].second; } for(int i=1; i<n; i++){ xMin1[i] = min(xMin1[i], xMin1[i-1]); xMax1[i] = max(xMax1[i], xMax1[i-1]); yMin1[i] = min(yMin1[i], yMin1[i-1]); yMax1[i] = max(yMax1[i], yMax1[i-1]); } for(int i=n-2; i>=0; i--){ xMin2[i] = min(xMin2[i], xMin2[i+1]); xMax2[i] = max(xMax2[i], xMax2[i+1]); yMin2[i] = min(yMin2[i], yMin2[i+1]); yMax2[i] = max(yMax2[i], yMax2[i+1]); } printf("%lld %lld %lld\n", xMax1[ansIdx] - ans, yMin1[ansIdx], ans); printf("%lld %lld %lld\n", xMin2[ansIdx+1], yMin2[ansIdx+1], ans); } else{ printf("%lld %lld %lld\n", xMin1[ansIdx], yMax1[ansIdx] - ans, ans); printf("%lld %lld %lld\n", xMin2[ansIdx+1], yMin2[ansIdx+1], ans); } }

Compilation message (stderr)

izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
izvanzemaljci.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%lld %lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.cpp: In function 'void solve1()':
izvanzemaljci.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%lld %lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.cpp: In function 'void solve2()':
izvanzemaljci.cpp:40:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     for(int i=0; i<n; i++) scanf("%lld %lld", &points[i].first, &points[i].second);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...