#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int check(vector<int> arr, int r)
{
int sum = 0;
int length = arr.size();
for(int i = 0; i < length; i++)
{
sum += abs(arr[i] - r);
}
return sum;
}
int binarySearch(vector<int> arr, int mini, int maxi)
{
int left = mini;
int right = maxi;
int min_sum = INT_MAX;
int best_r = INT_MIN / 2;
while(left <= right)
{
int middle = left + (right - left) / 2;
int curr_sum = check(arr, middle);
if(curr_sum < min_sum)
{
min_sum = curr_sum;
best_r = middle;
left = middle + 1;
}
else
right = middle - 1;
}
return best_r;
}
void solve()
{
int n;
cin >> n;
int maxi_x = 0, maxi_y = 0;
int mini_x = INT_MAX, mini_y = INT_MAX;
vector<int> X(n);
vector<int> Y(n);
for(int i = 0; i < n; i++)
{
cin >> X[i] >> Y[i];
maxi_x = max(maxi_x, X[i]);
mini_x = min(mini_x, X[i]);
maxi_y = max(maxi_y, Y[i]);
mini_y = min(mini_y, Y[i]);
}
int val1 = binarySearch(X, mini_x, maxi_x) ;//call for x
int val2 = binarySearch(Y, mini_y, maxi_y) ;//call for y
cout << val1 << ' ' << val2 << '\n';
}
int main(){
// #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
// // ll T;
// // cin >> T;
// // while(T--)
// // {
// // solve();
// // }
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
1832 KB |
Output is correct |
2 |
Incorrect |
75 ms |
1848 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
83 ms |
1832 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |