#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], yMax1[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], yMax2[i+1]);
yMax2[i] = max(yMax2[i], yMax2[i+1]);
}
ll justone = max(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], yMax1[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], yMax2[i+1]);
yMax2[i] = max(yMax2[i], yMax2[i+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 = 1;
}
/// 답 출력하기
if(justone <= ans || ansMode == -1){
printf("%lld %lld %lld\n", xMin1[n-1], yMin1[n-1], justone);
printf("%lld %lld %lld\n", INT_MAX, INT_MAX, justone);
}
else if(ansMode == 0){
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
izvanzemaljci.cpp: In function 'void solve2()':
izvanzemaljci.cpp:102:20: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
102 | printf("%lld %lld %lld\n", INT_MAX, INT_MAX, justone);
| ~~~^
| |
| long long int
| %d
izvanzemaljci.cpp:102:25: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'int' [-Wformat=]
102 | printf("%lld %lld %lld\n", INT_MAX, INT_MAX, justone);
| ~~~^
| |
| long long int
| %d
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
23 ms |
292 KB |
Output is correct |
| 8 |
Correct |
23 ms |
212 KB |
Output is correct |
| 9 |
Correct |
23 ms |
296 KB |
Output is correct |
| 10 |
Correct |
23 ms |
292 KB |
Output is correct |
| 11 |
Correct |
24 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int64 expected |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
