Submission #3215828
Source Code Expand
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define int long long
#define INF 1000000000000000000
using namespace std;
typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;
template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);
signed main(){
int N; cin >> N;
vec x(N), y(N);
REP(i, N) cin >> x[i] >> y[i];
int m = INF, M = 0;
REP(i, N){
m = min(m, min(x[i], y[i]));
M = max(M, max(x[i], y[i]));
}
int m2 = m, M2 = M;
REP(i, N){
m2 = max(m2, min(x[i], y[i]));
M2 = min(M2, max(x[i], y[i]));
}
int ans1 = (M - M2) * (m2 - m);
vector<Pii> p(N);
REP(i, N) p[i] = Pii(min(x[i], y[i]), max(x[i], y[i]));
SORT(p);
int l = p[N - 1].first - p[0].first;
int mm = INF, MM = p[N - 1].first;
REP(i, N){
mm = min(mm, p[i].second);
MM = max(MM, p[i].second);
int mm2 = mm;
if(i < N - 1) mm2 = min(mm, p[i + 1].first);
l = min(l, MM - mm2);
}
int ans2 = (M - m) * l;
cout << min(ans1, ans2);
return 0;
}
template<typename T>
void readvec(vector<T> &a){
REP(i, a.size()){
cin >> a[i];
}
}
void readindex(vector<int> &a){
REP(i, a.size()){
cin >> a[i];
a[i]--;
}
}
Submission Info
Submission Time |
|
Task |
E - Ball Coloring |
User |
sumitacchan |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
1624 Byte |
Status |
AC |
Exec Time |
181 ms |
Memory |
6528 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
700 / 700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0, example1, example2 |
All |
div20, div21, div22, div23, div24, example0, example1, example2, maxrand0, maxrand1, maxrand2, maxrand20, maxrand21, maxrand210, maxrand211, maxrand22, maxrand23, maxrand24, maxrand25, maxrand26, maxrand27, maxrand28, maxrand29, maxrand3, maxrand4, smallrand0, smallrand1, smallrand2, smallrand3, smallrand4, sparse0, sparse1, sparse2, sparse3, sparse4 |
Case Name |
Status |
Exec Time |
Memory |
div20 |
AC |
176 ms |
6528 KB |
div21 |
AC |
175 ms |
6528 KB |
div22 |
AC |
176 ms |
6528 KB |
div23 |
AC |
176 ms |
6528 KB |
div24 |
AC |
176 ms |
6528 KB |
example0 |
AC |
1 ms |
256 KB |
example1 |
AC |
1 ms |
256 KB |
example2 |
AC |
1 ms |
256 KB |
maxrand0 |
AC |
174 ms |
6528 KB |
maxrand1 |
AC |
175 ms |
6528 KB |
maxrand2 |
AC |
181 ms |
6528 KB |
maxrand20 |
AC |
176 ms |
6528 KB |
maxrand21 |
AC |
178 ms |
6528 KB |
maxrand210 |
AC |
177 ms |
6528 KB |
maxrand211 |
AC |
178 ms |
6528 KB |
maxrand22 |
AC |
178 ms |
6528 KB |
maxrand23 |
AC |
179 ms |
6528 KB |
maxrand24 |
AC |
176 ms |
6528 KB |
maxrand25 |
AC |
179 ms |
6528 KB |
maxrand26 |
AC |
179 ms |
6528 KB |
maxrand27 |
AC |
178 ms |
6528 KB |
maxrand28 |
AC |
178 ms |
6528 KB |
maxrand29 |
AC |
177 ms |
6528 KB |
maxrand3 |
AC |
174 ms |
6528 KB |
maxrand4 |
AC |
174 ms |
6528 KB |
smallrand0 |
AC |
1 ms |
256 KB |
smallrand1 |
AC |
1 ms |
256 KB |
smallrand2 |
AC |
1 ms |
256 KB |
smallrand3 |
AC |
1 ms |
256 KB |
smallrand4 |
AC |
1 ms |
256 KB |
sparse0 |
AC |
174 ms |
6528 KB |
sparse1 |
AC |
174 ms |
6528 KB |
sparse2 |
AC |
175 ms |
6528 KB |
sparse3 |
AC |
176 ms |
6528 KB |
sparse4 |
AC |
176 ms |
6528 KB |