[BOJ] 1711번: 직각삼각형

https://www.acmicpc.net/problem/1711


N이 애매해서 $N^3$도 돌아갈 것 같은 느낌을 주지만 아마 직접 돌려보면 시간초과가 뜰 것입니다. 대신 직각삼각형에서 90도가 되는 점을 하나 정하고, 나머지 점들을 vector로 생각해 직교하는 vector의 갯수를 센다고 생각해봅시다. 편의상 90도가 되는 점이 (0,0)에 위치하게끔 평행이동시켰다고 한다면, (a, b)점과 직교하는 vector는 Counter clock wise로 생각했을 때 (-b, a)이므로 gcd를 적절하게 취해 계산할 수 있습니다. 각도정렬을 하는 방식보다 이 방식이 코드의 길이가 훨씬 짧을 것 같네요.


https://github.com/blisstoner/BOJ/blob/master/1711.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 2236번: Team Selection  (0) 2018.11.13
[BOJ] 1762번: 평면그래프와 삼각형  (0) 2018.11.12
[BOJ] 13023번: ABCDE  (2) 2018.11.11
[BOJ] 10366번: Hari Merdeka  (0) 2018.10.16
[BOJ] 11690번: LCM(1, 2, ..., n)  (0) 2018.10.07
[BOJ] 3955번: Candy Distribution  (0) 2018.09.27
  Comments