This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(x) cout << #x << " " << x << endl;
#define pii pair<int, int>
const int inf = 1e9 + 10;
void solve1( vector<pii>& v ){
int x1 = inf, x2 = -inf, y1 = inf, y2 = -inf;
for( auto [x, y] : v ){
x1 = min( x1, x );
x2 = max( x2, x );
y1 = min( y1, y );
y2 = max( y2, y );
}
int tam = max( x2 - x1, y2 - y1 );
tam = max( tam, 1 );
cout << x1 << " " << y1 << " " << tam << endl;
}
struct rect{
int x, y, tam; rect( int x = 0, int y = 0, int tam = 0 ) :x(x), y(y), tam(tam) {}
};
void solve2( vector<pii>& v ){
sort( v.begin(), v.end(), [&]( pii a, pii b ){
return a.first < b.first;
}); // ordena por x;
vector<rect> resp( v.size() );
int x1 = inf, x2 = -inf, y1 = inf, y2 = -inf;
for( int i = 0; i < v.size(); i++ ){
auto [x, y] = v[i];
x1 = min( x1, x );
x2 = max( x2, x );
y1 = min( y1, y );
y2 = max( y2, y );
resp[i] = rect( x1, y1, max( x2 - x1, y2 - y1 ) );
resp[i].tam = max( resp[i].tam, 1 );
}
x1 = inf, x2 = -inf, y1 = inf, y2 = -inf;
rect a( 0,0, inf ), b( 0, 0, inf );
for( int i = v.size() - 1; i > 0; i-- ){
auto [x, y] = v[i];
x1 = min( x1, x );
x2 = max( x2, x );
y1 = min( y1, y );
y2 = max( y2, y );
rect cur( x1, y1, max( x2 - x1, y2 - y1 ) );
if( max( cur.tam, resp[i - 1].tam ) < max( a.tam, b.tam ) ){
a = cur;
b = resp[i - 1];
a.tam = max( a.tam, 1 );
b.tam = max( b.tam, 1 );
}
}
sort( v.begin(), v.end(), [&]( pii a, pii b ){
return a.second < b.second;
}); // ordena por y;
resp.clear();
resp.resize(v.size());
x1 = inf, x2 = -inf, y1 = inf, y2 = -inf;
for( int i = 0; i < v.size(); i++ ){
auto [x, y] = v[i];
x1 = min( x1, x );
x2 = max( x2, x );
y1 = min( y1, y );
y2 = max( y2, y );
resp[i] = rect( x1, y1, max( x2 - x1, y2 - y1 ) );
resp[i].tam = max( resp[i].tam, 1 );
}
x1 = inf, x2 = -inf, y1 = inf, y2 = -inf;
for( int i = v.size() - 1; i > 0; i-- ){
auto [x, y] = v[i];
x1 = min( x1, x );
x2 = max( x2, x );
y1 = min( y1, y );
y2 = max( y2, y );
rect cur( x1, y1, max( x2 - x1, y2 - y1 ) );
if( max( cur.tam, resp[i - 1].tam ) < max( a.tam, b.tam ) ){
a = cur;
b = resp[i - 1];
a.tam = max( a.tam, 1 );
b.tam = max( b.tam, 1 );
}
}
cout << a.x << " " << a.y << " " << a.tam << endl;
cout << b.x << " " << b.y << " " << b.tam << endl;
}
int main(){
int n, k; cin >> n >> k;
vector<pii> v(n);
for( int i = 0; i < n; i++ ) cin >> v[i].first >> v[i].second;
if( k == 1 ) solve1(v);
else if( k == 2 ) solve2( v );
}
Compilation message (stderr)
izvanzemaljci.cpp: In function 'void solve2(std::vector<std::pair<int, int> >&)':
izvanzemaljci.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for( int i = 0; i < v.size(); i++ ){
| ~~^~~~~~~~~~
izvanzemaljci.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for( int i = 0; i < v.size(); i++ ){
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |