[일반] 4181 무슨문제인가요?

[익명(106.101)]

Y인점들은 convexhull의 꼭지점이라는 건가요?
걍 Y인ㅅ섬 기준잡아서 반시계방향으로 정렬했더니 틀리던데
문제의도를 잘 모르겠어옷
Convexhull내부의 점이라면 Y인점들로 convexhull구하면 될테고

[익명(211.223)]

반례가 있음 예를 들어서 (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (1, 1)으로 답이 나와야 되는데 마지막에 원점으로 돌아오는 직선에 점이 3개 이상 있으니까 (0, 0) (1, 0) (2, 0) (2, 1) (1, 1) (2, 2) 이런식으로 나옴 그래서 마지막에 끝에서부터 CCW 값이 같은 구간은 뒤집어줘야 함

[익명(211.223)]

물론 실제 컨벡스헐 알고리즘에서는 이런 반례가 없음 왜냐하면 가장 외곽에 위치한 점 3개가 한 직선에 있으면 양 끝 두 점만 추출되니까 이 문제에 한해서만 반례 처리가 필요한거