Boj 3164) Pruge

문제

백준 3164

시간 복잡도

O(1)

설명

전략은 y=x 를 대각선으로 하는 정사각형 부분과 나머지 파트로 쪼개서 값을 구하는 것임.

• 정사각형 부분은 2번째 칸부터 채워져 있다면 등차수열의 합 공식으로 값을 계산할 수 있음.
  • a_n = 4*n-1 => sum(n) = n(2*n+1)
  • 1번째 칸부터 채워져 있으면 정사각형 넓이에서 위 공식으로 계산한 값을 빼주면 됨.
• 나머지 부분은 사각형의 시작점과 끝지점 그리고 처음부분의 사각형이 차있는지의 여부에 따라 계산할 수 있음.
  • 이때 정사각형의 4방향에 따른 4파트가 존재함
  • 하지만 실질적으론 L+T, L+R, B+T, B+R 의 4가지 경우 뿐임.(직접 그려보면 암)
  • 이때 구하는 L,B 와 T,R 이 겹치는 부분이 없게 범위조절을 해줘야함.

Input 만드는게 매우 쉬우므로 적은 범위의 Input 을 만들고, brute force 로 먼저 값을 구하고 (사각형 넓이인 O(n^2)), 이 값과 수식으로 푼 값을 비교해서 디버그하면 쉽게 해결할 수 있는 문제.

코드

using INT = int64_t;

int main()
{
	fastio;
	pair<INT, INT> lb, rt;
	cin >> lb.first >> lb.second >> rt.first >> rt.second;

	INT ans = 0, max_lb = max(lb.first, lb.second), min_rt = min(rt.first, rt.second);
	
	bool b_sq_start = max_lb % 2 == 1;
	bool b_sq_end = min_rt % 2 == 1;
	INT sq_len = (min_rt - max_lb) / 2;
	if (sq_len > 0)
	{
		//4*n-1 => n(2*n+1)
		if (!b_sq_start) ans += sq_len * (sq_len * 2 + 1);
		else ans += (min_rt - max_lb) * (min_rt - max_lb) - sq_len * (sq_len * 2 + 1);
	}
	else if (min_rt > max_lb) ans += b_sq_start * (min_rt - max_lb);
	
	if (lb.first < max_lb || rt.first < max_lb)
		ans += (min(max_lb, rt.first) - lb.first) * ((rt.second - lb.second + b_sq_start) / 2);
	else if (lb.second < max_lb || rt.second < max_lb)
		ans += (min(max_lb, rt.second) - lb.second) * ((rt.first - lb.first + b_sq_start) / 2);
	
	if (min_rt > max_lb)
	{
		if (rt.first > min_rt)
			ans += (rt.second - max(lb.second, max_lb)) * ((rt.first - min_rt + b_sq_end) / 2);
		else if (rt.second > min_rt)
			ans += (rt.first - max(lb.first, max_lb)) * ((rt.second - min_rt + b_sq_end) / 2);
	}
	
	cout << ans;
}