[백준] 1604번 정사각형 자르기

문제 : https://www.acmicpc.net/problem/1604

 

 

문제요약 : N개의 선분들이 (-10,-10)(-10,10)(10,10)(10,-10)으로 이루어진 정사각형을 몇개의 영역으로 나누는가?

 

조건 :

1. (-1000≤x1,y1,x2,y2≤1000)

2. 선분의 양 끝점은 정사각형 밖에 있다.

3. 두 선분은 같은 직선 상에 있지 않다.

4. 세 개 이상의 직선은 한 점에서 교차하지 않는다.

 

해설 :

 

사실 생각해보면 꽤 간단한 문제임을 알 수 있습니다.

선분이 아닌 직선으로 보았을 때 직선간의 교점의 수가 하나 늘 때마다 평면의 영역은 하나씩 늘게 됩니다.

마찬가지로 위 문제는 정사각형 영역만을 보았을 때 그 위를 지나가는 직선들간의 교점의 개수를 확인하면 됩니다.

 

교점의 개수 : http://www.gisdeveloper.co.kr/?p=89

 

i번째의 직선이 추가될 때 i-1번째의 상태에서 다른 직선들과 i번째 직선이 만나는 교점의 개수 +1을 ans에 더해주면 됩니다.

 

단, 교점이 x==-10 || x==10 || y==-10 || y==10인 경우 정사각형 영역을 나누지는 못하기 때문에 더해주지 않으면 됩니다.