2019-2020 ICPC, Asia Jakarta Regional - H. Twin Buildings(수학, 기하)

https://codeforces.com/problemset/problem/1252/H

바로 전에 포스팅한 문제의 풀이와 유사

 

<문제설명>

L*W로 표현되는 영역들이 주어진다. (L,W<=1e9) 이 영역들에 두 개의 A*B크기의 빌딩을 지으려고 한다. 빌딩 넓이의 최댓값을 구하라. (한 영역에 두 빌딩을 다 지어도 된다)

 

 

<풀이>

하나의 영역에 두 빌딩을 다 짓는 경우와 두 영역에 나눠 짓는 경우로 나눠 풀었다.

(하나의 영역에 두 빌딩을 다 짓는 경우는 쉬우니까 생략)

 

한 영역에 하나씩 빌딩을 두 개 지을 때 지을 수 있는 빌딩 크기의 최댓값은 어떻게 구할까?

 

i번 영역과 j번 영역에 빌딩을 짓는다면,

min(Li, Lj) * min(Wi, Wj)가 지을 수 있는 빌딩의 최대 크기일 것이다.

 

영역을 90도씩 돌려가며 생각해도 문제의 일반성을 해치지 않으므로, Li<=Wi를 강제해서 입력받는다.

 

그 후 Li크기를 기준으로 오름차순으로 정렬한다

 

i번째 영역에 빌딩을 지을때 최댓값을 갱신해가면 된다.

 

ans = max(ans, a[i].fisrt * min(a[i].second, sf[i + 1]));

 

앞선 포스팅의 그림처럼 그리면 형태가 바로 눈에 들어올 것.

 

<코드>

int n;
ll sf[MAX], ans, temp;
P a[MAX];

int main() {
	FAST; cin >> n;
	for (int i = 0; i < n; i++) {
		ll l, w; cin >> l >> w;
		if (l > w) swap(l, w);
		a[i] = { l,w };
		temp = max(temp, l * w);
		temp = max(temp, l * w);
	}
	sort(a, a + n);
	for (int i = n - 1; i >= 0; i--) 
		sf[i] = max(sf[i + 1], a[i].second);

	for (int i = 0; i < n; i++) {
		ll l, w;
		tie(l, w) = a[i];
		ans = max(ans, l * min(w, sf[i + 1]));
	}
	
	if (ans * 2 >= temp) cout << ans << ".0\n";
	else cout << temp / 2 << "." << (temp % 2 ? 5 : 0) << '\n';
}

 

 

<생각>

double은 유효숫자가 15자리이므로, 1e15를 넘어가는 값에 대한 연산은 loss가 너무 크다. 

 

최대 1e18에 대해 연산해야 하므로 double을 쓰면 안된 다는 점 유념