algospot 너드인가, 너드가 아닌가? (문제 ID: NERDS) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/NERDS

algospot.com :: NERDS

F= A * 신발 사이즈 + B * 분당 타이핑 속도 인 F가 있고 사람마다 신발사이즈와 분당 타이핑 속도가 주어졌을때 F가 일정 점수 이상인 사람을 너드로 추측한다고 하자.

사람마다 너드인지 여부와 신발 사이즈, 분당 타이핑 속도 이렇게 3가지 속성이 주어졌을때, 이 사람들의 너드 여부를 정확하게 추측할 수 있는 F= A * 신발 사이즈 + B * 분당 타이핑 속도 가 존재하는지를 예측 문제이다.

먼저 (신발 사이즈, 분당 타이핑 속도)를 (x,y)좌표로해서 점을 찍어보자.

이때 너드인 사람에 대해서 A*x + b*y >=T 가 성립해야 하므로 너드인점들과 너드가 아닌 점들을 나눌수 있는 직선이 존재해야 한다.

이것을 좀더 해결하기 쉽게 바꾸자면 너드인 점들로 이뤄진 볼록 다각형과 너드가 아닌점들로 이뤄진 볼록 다각형에 겹치는 부분이 있는지를 계산하면 된다.

그러기 위해서는 먼저 너드인 점과 너드가 아닌 점들을 각각 포함하는 볼록 다각형 두개를 만든다.

어느 한 다각형이 다른 다각형에 포함되거나, 두 다각형에 서로 닿는 두 변이 존재하는지를 확인한다.

포함여부를 확인할때는 어느 한 다각형의 꼭짓점 하나가 다른 다각형안에 있는지를 보면 되는데, 이것은 꼭짓점에서 반직선을 그어 다각형의 변과 교차하는 점을 확인하면 된다.

교하는 점의 갯수가 홀수면 꼭짓점은 다른 다각형 안에있고 짝수면 밖에있다. 

이때 주의할 점은 반직선이 다각형의 꼭짓점을 지날때인데 이것을 처리하기 위해서 반직선을 살짝 올린다는 개념으로 가로지르는지를 확인할때 부등호를 생략한다.

그러면 다각형의 꼭짓점 기준 위에 선분은 교차하고 아래 선분은 교차하지 않는것으로 처리되어 정상작동하게 된다.

 

코드원본: https://github.com/sbl133/JongmanBook/blob/main/15.%20ComputationalGeometry/NERD.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1