hsnks100   9달 전

통과가 안되네요.


도움좀 부탁드립니다.

이걸로 해결이 될진 모르겠지만, 이 문제에서 직선도 컨벡스 헐로 허용되는 듯합니다.

hsnks100   9달 전

그래서 

9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3


라는 데이터도 테스트 해보니 4로 정상적으로 잘 나옵니다.

아뇨 말 그대로 직선이요.

3

1 1

2 2

3 3

에 대해서 3이 아닌 2를 출력하는 코드로 AC가 뜹니다. 물론 저런 데이터가 있을지는 모르겠습니다..

hsnks100   9달 전

직선일 때는 2를 출력해야 맞는건가요?


직선일 때는 printf 에 max 만 빼주면 항상 2로 들어갑니다.

하나의 직선 위에 모든 점이 있을 때는 2를 출력해보세요

hsnks100   9달 전

그 경우도 검토 되어있습니다.


4

1 1

2 2

3 3
4 4


3

1 1

2 2

3 3 

모두 2를 출력합니다.

위 코드에서 anglegt 함수와 left 함수를 아래와 같이 수정하니 맞네요

left 함수는 일반적인 ccw 함수로 변경 + double 반환으로 변경

anglegt 함수는 basepoint와의 상대적 위치 대신 basepoint와의 각도를 기준으로 정렬(각도는 O(n)으로 메인 내에서 전처리)

anglegt만 고쳤을 땐 정답이 안나온 것으로 보아 최소한 left 함수에는 문제가 있는 듯합니다.

hsnks100   9달 전

anglegt 가 일단 각도로 정렬하고 각도도 같으면 거기서 거리로 구별합니다.

문제 없어보이는데 ㅇ... 다른문제가 있었나요?


left 함수가 ccw 함수라고 생각하는데 좀 더 검토를 해봐야겠네요.

hsnks100   9달 전

말씀대로 left 가 문제가 있었던것 같습니다. 감사합니다.

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