steve14914   2년 전

점들을 point 안에 담았습니다. x, y는 좌표이고, tx, ty는 후반에 볼록다각형을 찾을 때에 사용될 임시 좌표입니다.

점들을 입력 받은 뒤에 두 볼록다각형의 선분들의 교차 여부를 cross함수로 찾아 교점들을 line_up_points에 넣었습니다. 선분 2개를 각각 직선의 방정식으로 나타내고 교점이 두 선분 모두 위에 있나 확인해서 교차 여부를 확인합니다.

in 함수는 n의 꼭짓점이 볼록다각형 m 안에 있는지, m의 꼭짓점이 볼록다각형 n 안에 있는지 찾기 위한 함수입니다. 다각형의 각 선분을 직선의 방정식으로 나타내고 경우에 따라 위에 있는지, 아래에 있는지 모든 선분들에서 조사하여 내부에 있는지 판별합니다.

그 후에는 다각형 내부에 있는 점들, 교차점들을 담은 line_up_points 의 점들을 반시계방향으로 정렬합니다. 가장 오른쪽 아래에 있는 점을 기준으로 잡고(tx, ty를 0,0으로 설정) 나머지 점들의 tx, ty를 기준점의 x, y만큼 각각 뺍니다. 그 후 각 점들의 cos값을 크기순으로 정렬하여 큰 순서대로 ans list에 담습니다. 각도가 180을 넘어갈 수 없기 때문에(가장 오른쪽 아래 점을 기준으로 잡았기 때문에) 찾은 cos값은 각도가 커질수록 작아질 것입니다.

그 후 ans의 점들을 신발끈 공식으로 넓이를 구합니다.

결과는 "틀렸습니다" 입니다.

문제점을 지적해주시거나 반례를 찾아주세요

댓글을 작성하려면 로그인해야 합니다.