백준 1087번 문제 쥐잡기 풀이

https://www.acmicpc.net/problem/1087

1087번: 쥐 잡기

 

백준저지 1087번 문제 쥐 잡기 문제입니다.

 

이 문제는 삼분탐색이라는 알고리즘 개념을 공부한 뒤, 처음으로 8986번 전봇대 문제를 풀어보고, solved.ac에서 같은 카테고리에 있는 문제들 중 하나를 골라서 푼 경우라서, 쥐 잡기 문제가 삼분탐색 문제라는 것을 알고 접근했네요.

 

 

삼분탐색 문제는 알고리즘 구현 자체는 쉬운데, 아이디어를 생각해내기가 어렵다는 것 같았습니다.

 

문제 내용을 보면, 쥐들이 t가 변화함에 따라 마구잡이로 움직이게 되는데, 이 때 쥐들을 한꺼번에 잡을 수 있는 가장 작은 크기의 우리의 크기를 구하면 될 것 같아 보입니다.

 

쥐의 속도가 있는 경우 중 가장 작은 경우가 //(v=1//)인 경우이므로, 좌표의 가장 작은 값 부터 가장 큰 값까지가 -1000과 +1000이므로, //(t=2000//)를 가장 마지노선으로 두고 삼분탐색을 실시하면 답을 구할 수 있습니다.

 

쥐들이 어느 순간에는 가장 모이고, 그 이후에 다시 멀어지는 분포를 따를 것이므로, 필요한 우리의 크기는 아래로 볼록한 유니모달(unimodal) 그래프가 될 것임을 예측해볼 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
struct Pos { double x, y; };
Pos p[55], v[55];
int n;
double f(double t) { //시간이 t초 지났을 때, 모든 쥐를 다 잡을 수 있는 최소 우리 크기
	double ret = 0;
	Pos low, high;
	high = low = { p[0].x + t * v[0].x, p[0].y + t * v[0].y };
	for (int i = 1; i < n; i++) {
		low.x = min(low.x, p[i].x + t * v[i].x);
		low.y = min(low.y, p[i].y + t * v[i].y);
		high.x = max(high.x, p[i].x + t * v[i].x);
		high.y = max(high.y, p[i].y + t * v[i].y);
	}
	double x, y;
	x = high.x - low.x;
	y = high.y - low.y;
	return max(x, y);
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> p[i].x >> p[i].y >> v[i].x >> v[i].y;
	}
	double low = 0;
	double high = 2000;
	for (int i = 0; i < 100 && low < high; i++) {
		double a = (low * 2 + high) / 3;
		double b = (low + 2 * high) / 3;
		if (f(a) < f(b)) {
			high = b;
		}
		else {
			low = a;
		}
	}

	printf("%.11lf\n", f(low));
	return 0;
}

 

---

https://blog.naver.com/kks227/221432986308