BOJ 13310 | 먼 별

Convex Hull, Rotating Callipers에 대해 완전히 이해하고 있는 상태로 시도해야 풀 가능성이 보이는 문제다.

만약 삼분 탐색이 쓰인다는 것을 알고 있다면 이 문제는 단순한 구현 문제가 되겠지만, 실제로 이 문제를 보자마자 삼분탐색이라고 바로 알아채기는 쉽지 않다.

나는 이 문제 자체를 예전부터 알고는 있었기 때문에 삼분 탐색이라는 걸 스포당했지만, 사실 직관적으로 보면 삼분 탐색이 가능할 것 같아 보인다.

별의 이동 경로는 직선이다.

그러므로 두 별의 거리는 직선 그래프로 나타난다.
정확히는 V자 그래프, / 자 그래프 중 하나로 나올 것이다.

그러므로 모든 별들에 대한 그래프들을 전부 겹쳐서 최댓값만을 뽑아준 게 최종 그래프가 될 것이므로 이 그래프는 삼분 탐색이 가능하다.

평평한 구간에 대해서는 기울기가 0인 /자 그래프가 존재할 때 등장하는데, 그것보다 더 작은 값이 가장 먼 별의 거리로 채택될 수가 없다. (기울기가 0이므로 모든 시간에서 같은 거리로 유지된다.)

난 여기까지 생각하고 구현했다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);
#define ll long long

#define debug if constexpr (local) std::cout
#define endl '\n'

ll fx, fy;

struct Dot{
	ll x, y;
	ll dx, dy;
};

bool cmp(Dot a, Dot b){
	if (a.y != b.y) return a.y < b.y;
	return a.x < b.x;
}

bool _cmp(Dot a, Dot b){
	ll l = (b.x - fx) * (a.y - fy);
	ll r = (a.x - fx) * (b.y - fy);
	if (l != r) return l < r;
	
	if (a.y != b.y) return a.y < b.y;
	return a.x < b.x;
}

ll ccw(Dot a, Dot b, Dot c){
	return (b.x-a.x)*(c.y-b.y)-(c.x-b.x)*(b.y-a.y);
}

ll getDist(vector<Dot> stars){
	if (stars.size() == 2){
		ll dist = (stars[0].x-stars[1].x)*(stars[0].x-stars[1].x)+(stars[0].y-stars[1].y)*(stars[0].y-stars[1].y);
		return dist;
	}
	
	// Graham Sort
	sort(stars.begin(), stars.end(), cmp);
	fx = stars[0].x; fy = stars[0].y;
	sort(stars.begin()+1, stars.end(), _cmp);
	/*debug << "Graham Sort" << endl;
	for (auto &i: stars){
		debug << i.x << ' ' << i.y << endl;
	}*/
	
	// Convex Hull
	vector<Dot> task; task.push_back(stars[0]); task.push_back(stars[1]);
	int sz = stars.size();
	for (int i = 2; i < sz; i++){
		Dot next = stars[i];
		while (task.size() >= 2){
			Dot A = task[task.size()-2];
			Dot B = task[task.size()-1];
			task.pop_back();
			if (ccw(A, B, next) > 0){
				task.push_back(B);
				break;
			}
		}
		task.push_back(next);
	}
	//debug << "Convex Hull" << endl;
	/*for (auto &i: task){
		debug << i.x << ' ' << i.y << endl;
	}*/
	
	// Rotating Callippus
	//reverse(task.begin(), task.end());
	sz = task.size();
	Dot a1 = task[0]; Dot a2 = task[1];
	Dot a3 = task[1]; Dot a4 = task[2];
	ll idx = 1;
	ll maxdist = 0;
	for (int i = 0; i < sz; i++){
		a1 = task[i]; a2 = task[(i+1)%sz];
		
		while (ccw(a1, a2, {a4.x-(a3.x-a2.x), a4.y-(a3.y-a2.y)}) > 0 ){
			idx++;
			a3 = task[idx%sz]; a4 = task[(idx+1)%sz];
		}
		
		ll dist = 0;
		dist = (a1.x-a3.x)*(a1.x-a3.x) + (a1.y-a3.y)*(a1.y-a3.y);
		
		if (maxdist < dist) maxdist = dist;
	}
	//debug << "Rotating Callippus" << endl;
	
	return maxdist;
}

int main(){
	int N, T; cin >> N >> T;
	vector<Dot> stars;
	for (int i = 0; i < N; i++){
		int x, y, dx, dy;
		cin >> x >> y >> dx >> dy;
		stars.push_back({x, y, dx, dy});
	}
	
	//debug << "DBG " << getDist(stars) << endl;
	
	//Ternary Search
	ll lo = 0; ll hi = T;
	while (hi-lo >= 3){
		ll lmid = (lo*2+hi)/3;
		ll rmid = (lo+hi*2)/3;
		
		vector<Dot> lstars;
		vector<Dot> rstars;
		
		for (auto &i: stars){
			lstars.push_back({i.x + i.dx*lmid, i.y + i.dy*lmid, i.dx, i.dy});
			rstars.push_back({i.x + i.dx*rmid, i.y + i.dy*rmid, i.dx, i.dy});
		}
		
		ll ldis = getDist(lstars);
		ll rdis = getDist(rstars);
		
		//debug << "DBG " << getDist(lstars) << getDist(rstars) << endl;
		
		if (ldis > rdis) lo = lmid;
		else hi = rmid;
	}
	
	//debug << lo << ' ' << hi << endl;
	
	ll mndis = 1e18;
	ll mnidx = 0;
	for (int k = lo; k <= hi; k++){
		vector<Dot> fstars;
		for (auto &i: stars){
			fstars.push_back({i.x + k*i.dx, i.y + k*i.dy, i.dx, i.dy});
		}
		
		//debug << "FSTARS" << endl;
		/*for (auto &i: fstars){
			debug << i.x << " " << i.y << endl;
		}*/
		
		ll tdis = getDist(fstars);
		if (tdis < mndis){
			mndis = tdis;
			mnidx = k;
		} 
	}
	
	cout << mnidx << endl;
	cout << mndis << endl;
	
}