백준 23239 당근밭

백준 당근밭 문제

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

문제 설명

당근밭에 직사각형 마구간이 있고, 왼쪽 아래 모서리에 말이 묶여있다
오른쪽 그림과 같이 말은 마구간을 가로지를 수 없고 줄의 길이를 반지름으로 하여 움직일 수 있다고 할 때 최대로 먹을 수 있는 당근의 수를 구하는 문제
(당근은 모든 격자점에 하나씩 심어져있음)
(마구간의 가로 세로 w, h, 줄의 길이 l)

풀이

네가지 경우로 나눠서 풀었다
만약 w가 h보다 작다고 가정할 때

1. 줄의 길이 l이 w보다 작음
   
2. w < l <=h
   
3. h < l <= w+h
   
4. w+h < l
   

그림과 같은 영역에서 당근을 먹을 수 있다
2,3,4분면 당근 수는 동일하고 1사분면 당근 수만 다르게 구하면 된다.

원의 반지름이 l일 때 for문으로 y축 0부터 l까지 돌면서 가로^2 + 세로^2 <= l^2인지 판단하여 각 y마다 가질 수 있는 x의 최대를 구해주고 이를 전부 더하면 원 1/4에 속하는 점의 수를 구할 수 있음

void make_max(int l){ //l : 반지름  
	int tmp_h = l;
	int power = l*l;
	for(int i=0;i<=l;i++){ //y가 0부터 L까지 돈다  
		if(i*i + tmp_h*tmp_h<=power){ //포함됨  
			max_bar[i] =tmp_h;
		}else{ //미포함  
			tmp_h --; 
			i--;
		} 
	}
}

4번 그림과 같이 두 원이 겹치게 된다면,,
y축을 저장할 때 최대 x를 저장하게 하여 바깥 테두리에 속하는 점을 구한 후 마굿간 넓이의 당근을 빼주면 됨...

코드

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;

int max_bar[100001];
long long sum = 0;

void make_max(int l){ //l : 반지름  
	int tmp_h = l;
	int power = l*l;
	for(int i=0;i<=l;i++){ //x가 0부터 L까지 돈다  
		if(i*i + tmp_h*tmp_h<=power){ //포함됨  
			max_bar[i] =tmp_h;
		}else{ //미포함  
			tmp_h --; 
			i--;
		} 
	}
}
int main(){
	int w,h,L;
	scanf("%d %d %d",&w,&h,&L);
	
//	for(int i=0;i<=L;i++){
//		printf("%d ",max_bar[i]);
//	}
	make_max(L);
	long long tmp = 0;
	for(int i=1;i<=L;i++){
		tmp+=max_bar[i];
	}
//	printf("%lld ",tmp);
	sum+= (long long)tmp*3 + 2*L; //3분면 계산 
//	printf("sum :%lld \n",sum);
	 //w <= h라 가정하면 
	int ttmp = 0;
	if(w > h){
		ttmp = h;
		h = w;
		w = ttmp;
	}
	
	// 1. L <=w
	if(L<=w){

	}else if(L<=h){
		// 2. w < L <= h
		make_max(L-w);
		for(int i=0;i<=L-w;i++){
			sum+=(long long)max_bar[i];
		}
		
	}else if( L < w+h ){
		// 3. h < L < w+h 
		make_max(L-h);
		for(int i=0;i<=L-h;i++){
			sum+=(long long)max_bar[i];
		}
		make_max(L-w);
		for(int i=0;i<=L-w;i++){
			sum+=(long long)max_bar[i];
		}

	}else{
		// 4. w+h < L 
		memset(max_bar, 0, sizeof(max_bar));
		int tmp_h = L-h; //x좌표 최대  
		int power = (L-h)*(L-h);
		for(int i=0;i<=L-h;i++){ //y가 0부터 L까지 커짐  
			if(i*i + tmp_h*tmp_h<=power){ //포함됨  
				max_bar[i] =max(max_bar[i],tmp_h+h); 
			}else{ //미포함  
				tmp_h --; 
				i--;
			} 
		}
		tmp_h = L-w; //x좌표 최대  
		power = (L-w)*(L-w);
		for(int i=0;i<=L-w;i++){ //y가 0부터 L까지 커짐  
			if(i*i + tmp_h*tmp_h<=power){ //포함됨  
				max_bar[i+w] =max(max_bar[i+w],tmp_h); 
			}else{ //미포함  
				tmp_h --; 
				i--;
			} 
		}
		for(int i=1;i<=L;i++){
			sum+=(long long)max_bar[i];
		}
		sum-=w*h;
		sum+=2 * L -w-h;

	}
	printf("%lld",sum);
	return 0;

}