Expert스터디 1일차(2016.05.26)

• qsort 구현 연습 (같은 원소 처리에 주의) + 자신만의 rand()
• 오일러 피 함수 구현 연습 ( pi(1)부터 pi(n)까지 구하기 ) -> 익힌 후 10438 풀어보기

• ccw 함수 = 신발끈 공식 (shoelace)

  • http://cookyworld.tistory.com/49
• Utopia, 분수 찾기 생각해보기

- 학습내용

1. CCW(CounterClockWise)를 통한 2차원 좌표에 order를 부여하고, 정렬하기.

atan 를 이용하는게 제일 쉽지만, 라이브러리를 못쓰므로 CCW로 정렬.

CCW라는게 사실 외적인데, 외적의 부호로 결정한다.

두점으로 만든 선분을 기준으로 나머지 한점이 시계방향인지, 반시계방향인지, 일직선위에 있는지를 판별. 

2. Euler Phi function을 통한 서로소 찾기

서로소 구하는 함수이고, comm, multi가 성립한다.

phi(p) = p-1 이고(prime p)

phi(n) = ∑_(p|n) phi(p)라는데 이게 어디에 쓰이는지는 잘 모르겠다.

신기한 팁은. 

기약분수의 갯수 = 전체 분수의 갯수 - 약수의 기약분수의 갯수. 이고 기준점이 변동가능하다는거.

문제번호(www.acmicpc.net)

1. 2076

 

2. 1882

3. 5496(어려움)

4. 10438