BOJ 12294 Drummer (Large)

문제 링크입니다.

문제 요약

주어진 수열과 원소 간 최대 차이가 가장 적은 등차수열을 찾으세요.

풀이

수열의 $i$번째 원소를 평면 위의 점 $(i, a[i])$로 표현합니다. 같은 방식으로 등차수열은 평면 위에서 직선의 형태로 나타낼 수 있습니다.

직선의 기울기를 결정했다면 오차는 그 기울기의 직선을 수열을 표현하는 점들의 볼록 껍질의 위아래로 접하게 긋는 식으로 결정할 수 있습니다.

볼록 껍질의 변을 이루는 선분의 기울기가 정답 후보가 됩니다. 회전하는 캘리퍼스를 적당히 활용하면 테스트 케이스 당 $O(N \lg N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;

#define x first
#define y second
pll operator+ (pll a, pll b){return {a.x+b.x, a.y+b.y};}
pll operator- (pll a, pll b){return {a.x-b.x, a.y-b.y};}
pll operator+= (pll& a, pll& b){return a = a+b;}
pll operator-= (pll& a, pll& b){return a = a-b;}
ll dist(pll a, pll b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
ll outer(pll a, pll b){return a.x*b.y-b.x*a.y;}

ll ccw(pll a, pll b, pll c){
	auto ret = outer(b-a,c-a);
	return (ret>0)-(ret<0);
}
ll cccw(pll a, pll b, pll c, pll d){
	return ccw(a, b, d-(c-b));
}

vector<pll> ConvexHull(vector<pll> &v){
	sort(v.begin(), v.end());
	if(v.size() <= 2) return v;
	vector<pll> up, down;
	for(auto &p : v){
		while(up.size() >= 2 && ccw(up[up.size()-2], up[up.size()-1], p) >= 0)
			up.pop_back();
		up.push_back(p);
		while(down.size() >= 2 && ccw(down[down.size()-2], down[down.size()-1], p) <= 0)
			down.pop_back();
		down.push_back(p);
	}
	down.insert(down.end(), up.rbegin()+1, up.rend()-1);
	return down;
}

vector<pll> hull; ld ans;

void solve(){
	int n; cin >> n; vector<pll> p;
	for(int i = 1; i <= n; i++){int t; cin >> t; p.push_back({i, t});}
	ans = p.back().second-p.front().second; hull = ConvexHull(p);
	for(int i = 0, j = 1; i < hull.size(); i++){
		while(cccw(hull[i], hull[(i+1)%hull.size()], hull[j%hull.size()], hull[(j+1)%hull.size()]) > 0) j++;
		ld A = hull[(i+1)%hull.size()].second-hull[i].second;
		A /= hull[(i+1)%hull.size()].first-hull[i].first;
		ld B = hull[i].second-A*hull[i].first;
		ld tmp = abs(A*hull[j%hull.size()].first+B-hull[j%hull.size()].second);
		ans = min(ans, tmp);
	}
	cout << fixed << setprecision(12) << ans/2 << '\n';
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int T; cin >> T; for(int tc = 1; tc <= T; tc++) cout << "Case #" << tc << ": ", solve();
}