AtCoder Beginner Contest 224 참여후기 (ABC 224)

Contest : https://atcoder.jp/contests/abc224

Editorial : https://atcoder.jp/contests/abc224/editorial

코드 : https://github.com/NaHwaSa/AtCoder/tree/master/ABC224

 

  망함. 일정 설정 해놓고 까먹었다가 거의 1시간 지나고 참여함. 근데 일단 C번에서 엄청 오래걸렸어서 변명밖에 안되긴 함. 어차피 Editorial 있으니 그냥 푼 A,B,C에 대한 후기만 적음.

 

A : 그냥 코딩이라는걸 할 줄 알면 풀 수 있을듯

 

B : 마찬가지로, 주어진 조건 대로 시뮬레이션만 구현 가능하면 풀 수 있음.

 

C : 설마 Beginner라고 달아두고 C번부터 기하학 CCW 문제가 나올줄은 몰랐음. 일단 O(N^3)으로 전부 확인하는 것 까진 쉽게 생각했는데, 삼각형 판정을 암만 해보려 해도 잘 안됬음. 뭐 결국 첫번째와 두번째로 고른 녀석들과 세번째가 각도가 동일하지 않으면 된다고 생각해서, 일단은 각도로 계산해봄. 당연히 저렇게 큰 정수에 double로 계산되니 (각도 구하기 위해 나누기 연산 들어가니깐) 오차가 커져서 제대로 안됨. 그 다음은 가장 긴 변 보다 나머지 두 변이 길기만 하면 되는데, 길이 구하려면 결국 스퀘어루트가 들어가야 하고.. 그럼 마찬가지로 double로 되면서 저렇게 큰 정수에 대해서는 오차가 커져서 정상적으로 판단이 안됨.

  결국 정수 수준에서 각도나 길이 계산이 가능해야 했는데, 마치기 10분 남기고 CCW가 떠올라서 그거 공식 찾아서 풀었음. CCW에 대한 이해는 아직 안되있으므로 풀이는 불가하고, CCW로 검색해보시면 확인 가능! 있는건 알고 있어서 가끔씩 공식 찾아 푸는 문제도 있긴한데 기하학은 어려워서 이해는 잘 못하겠음.. 수학 공부 해야지 ㅠ

  결국 3개의 점이 이루는 각도를 확인하는건데, 이 값이 0일 경우 동일선상에 있다고 볼 수 있고, double까지 안넘어가고 정수로 끝나므로 이 문제를 풀기 적합함.