사각형과 원이 겹치는 영역의 좌표의 개수는 O(N)에 구할 수 있을까

21676번: Газон (acmicpc.net)

 

왼쪽 아래 (x1,y1), 오른쪽 위 (x2,y2)로 주어지는 사각형과 중심 (x3,y3), 반지름 r로 주어지는 원이 서로 겹치는 영역의

 

정수 점 (x,y)의 개수를 구하는 문제

 

정말 단순하게 생각하면 사각형 안의 모든 정수 점 (x,y)에 대하여 원의 방정식 내부 (x-x3)**2 + (y-y3)**2 <= r**2를 만족하는지 체크하면 되는 문제

 

def check(x,y):
    
    v = (x-x3)**2 + (y-y3)**2

    if v <= (r**2):
        
        return True
    
    else:
        
        return False

x1,y1,x2,y2 = map(int,input().split())
x3,y3,r = map(int,input().split())

count = 0

for x in range(x1,x2+1):
    
    for y in range(y1,y2+1):
        
        if check(x,y):
            
            count += 1

print(count)

 

 

하지만 x1,x2,y1,y2,x3,y3의 범위가 -10만~10만이라 $O(N^{2})$은 시간초과가 날수밖에 없다

 

하지만... 이것말고 방법이 있나?

 

x를 정했으면 그거에 대해 y는 모든 범위를 돌아봐야할텐데..?

 

방법은 원의 방정식은 (x-x3)**2 + (y-y3)**2 = r**2로 알고 있기 때문에, x좌표를 안다면 원 둘레에 있는 y좌표를 알 수 있다

 

 

 

x1부터 x2 사이의 모든 x에 대하여 원 내부에 있는 x만을 대상으로 하고, 이 x에 대하여 원의 방정식으로 y좌표 a,b를 찾으면 된다

 

 

원 내부에 있는 x는 어떻게 찾아?

 

원 내부에 있는 x값들은 [x3-r, x3+r]이다.

 

 

따라서 x1부터 x2사이의 x에 대하여 [x3-r,x3+r]을 만족하는 x만을 대상으로, 원의 방정식에서 y좌표 a,b를 찾으면 된다

 

 

다음 문제는 정확히 직사각형 내부에 있는 점의 개수만 세야하는데

 

a,b가 어디에 있느냐에 따라 달라진다

 

[y1,y2]와 비교해서 b가 y1보다 작은 경우, a가 y2보다 작다면 a-y1+1개 있는거고

 

a가 y2보다 크다면? y2-y1+1개만큼 있는거고

 

b가 y1보다 큰데 y2보다 작다면? a가 y2보다 작다면 a-b+1개 있는거고

 

a가 y2보다 크다면 y2-b+1개 있는거고

 

 

 

 

 

뭔가 비교가 어렵고 문제가 생길것 같다면... (x1,y1)을 (0,0)으로 평행이동하는 것도 방법이다

 

(x1,y1)을 (0,0)으로 이동시키면 다른 점도 -x1, -y1만큼 이동하면 된다..

 

여기서 착각했던게 x1,y1이 음수라면 +x1,+y1 이런거 해야하느냐 이런 생각했는데...

 

조금만 생각해보면 그냥 -x1,-y1하면 된다는거 알 수 있고

 

x1,y1,x2,y2 = map(int,input().split())
x3,y3,r = map(int,input().split())

x2 -= x1
x3 -= x1
y2 -= y1
y3 -= y1

count = 0

for x in range(x2+1):
    
    if x >= x3-r and x <= x3+r:
        
        v = (r**2 - (x-x3)**2)**(1/2)
        v = int(v)
        
        a = v + y3
        b = -v + y3

        if b < 0:
            
            if a > y2:
                
                count += (y2+1)
            
            elif a >= 0:
                
                count += (a+1)
        
        elif b <= y2:
            
            if a > y2:
                
                count += (y2-b+1)
            
            else:
                
                count += (a-b+1)
        
                
print(count)

 

 

 

근데 a,b 구할때 위에서는 (r**2 - (x-x3)**2)**(1/2)를 구하고, 얘를 int() 취하고 y3과 더하거나 뺐는데

 

아래처럼 (r**2 - (x-x3)**2)**(1/2)에 y3를 더하거나 뺀 다음, int()를 취하면 틀리더라고

 

왜 틀린지 생각해보면.. float + int를 하면서 결과에 부동소수점 오차가 생겨서

 

최종 int()한 값이 실제 정수보다 1이 더 작다거나.. 그런 오차가 생긴듯?

 

예를 들어 원래 20이어야하는데 더했더니 19.999999999999999998 이런식으로 나와가지고

 

int()하면 19가 나오는거지.. 이런 경우 많았잖아

 

for x in range(x2+1):
    
    if x >= x3-r and x <= x3+r:

        a = (r**2 - (x-x3)**2)**(1/2) + y3
        b = -(r**2 - (x-x3)**2)**(1/2) + y3

        a = int(a)
        b = int(b)