티스토리 뷰

ICPC/2014 인터넷예선

F. Intersections

전명우 2014.11.11 14:49

2차원 좌표계에 모든 변이 x축과 평행하거나 y축에 평행한 직사각형 하나와 선분 하나가 주어졌을 때 교차점의 개수를 구하는 문제다.


이 문제를 편하게 해결하기 위해 두 선분이 주어졌을 때 생기는 교차점의 개수를 세는 함수 intersect(line a, line b)를 생각하자.


두 선분이 서로 다른 직선 성분일 경우, ccw 함수를 이용하여 두 선분이 교차하는지 확인할 수 있다. 만약 교차하면 생기는 교차점의 개수는 1개이며, 교차하지 않는다면 교차점의 개수는 0이다.


ccw(point a, point b, point c): (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y)

점 a에서 점 b로 갔다가 점 c로 갔을 때 꺽이는 방향이 시계 방향인지 반시계 방향인지 판별하는 함수

(값이 양수인 경우 반시계 방향, 값이 음수인 경우 시계 방향, 값이 0인 경우 세 점이 한 직선 위에 있음.)


두 선분이 같은 직선 성분일 경우, 교차점의 개수가 무한할 수 있다. 두 선분이 점에서 만나는 경우 교차점의 개수는 1개이며, 선에서 만나는 경우 교차점의 개수는 무한이다. 이 경우 계산을 편하게 하기 위해 선분의 양 끝 점 좌표의 x, y 성분을 더하여 1차원 좌표계로 표현할 수 있다.


intersect 함수 구현에 대한 자세한 설명은 생략한다. 함수가 구현이 되면, 직사각형을 구성하는 선분들과 주어진 선분과 교차점 개수를 구해 더한다. 이 때, 같은 교차점이 중복으로 세어질 수 있는데, 이런 경우 그 교차점은 직사각형의 꼭지점이 된다. 따라서, 직사각형 꼭지점이 선분 위에 있는 경우 세어준 값을 하나 감소시킨다.



'ICPC > 2014 인터넷예선' 카테고리의 다른 글

F. Intersections  (3) 2014.11.11
I. Stains  (0) 2014.11.11
J. Switch Array  (0) 2014.10.08
K. Traffic Jams  (0) 2014.10.08
G. Mutation  (0) 2014.10.08
E. Highway  (0) 2014.10.07
댓글
댓글쓰기 폼