[백준] 2285 우체국💫

백준 2285 우체국

• https://www.acmicpc.net/problem/2285

• 우체국으로부터 각 사람들까지의 거리의 합은 볼록 함수의 형태를 한다
  -> 삼분 검색(ternary search)을 통해 볼록 함수의 최소치를 구할 수 있다

• 맞왜틀 ~~~!!

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long int ll;

int N;
vector<ll> X, A;

//우체국의 위치가 location일 때 각 사람들까지의 거리의 합
ll getDistSum(ll location) {
	ll distSum = 0;

	for (int i = 0; i < N; ++i)
		distSum += (abs(location - X[i]) * A[i]);

	return distSum;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; ++i) {
		ll x, a;
		cin >> x >> a;
		X.push_back(x);
		A.push_back(a);
	}

	//삼분 탐색 (X의 경계값도 답에 포함되도록 hi + 1, lo - 1)
	double hi = 1000000000 + 1;
	double lo = -1000000000 - 1;

	for (int it = 0; it < 100; ++it) {
		double mid1 = (2*lo + hi) / 3;
		double mid2 = (lo + 2*hi) / 3;

		if (getDistSum(mid1) > getDistSum(mid2))
			lo = mid1;
		else hi = mid2;
	}

	ll res = (lo + hi) / 2;
	cout << res;
	return 0;
}