Algorithm/Computational Geometry (3) 썸네일형 리스트형 BOJ 1485: 정사각형 각 점들에 대한 길이를 모두 s배열에 저장하면 정사각형 네변의 길이, 대각선 2개 총 6개의 길이를 저장합니다. 이를 오름차순으로 정렬하면 대각선 2개에 대한 길이는 자연스럽게 뒤에 위치하게 됩니다. 이제, 앞에 4개 길이가 같은지 판별하고, 뒤에 2개 대각선길이가 서로 같다면 정사각형이라는 의미이므로 True를 리턴해줍니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include #include using namespace std; struct POINT { int x, y; }; POINT point[4]; int s[6]; int abss(int a) { return .. BOJ 6439번: 교차 입력으로 주어진 선분과 직사각형이 교차하는지를 판별하는 문제이다. 직사각형의 좌표들가 대각선으로 2개 들어오는데, x, y좌표를 각각 크기 비교해서 사용해야하는데 당연히 작은게 우선 들어올거라 판단해 여러번 틀린 문제였다. 이 문제는 크게 2가지 기준을 통과하면 T로 판별하게 하였다. 먼저, 직사각형 점들을 저장해주고, CCW로 선분이 직사각형 4개의 변과 교차하는지 판별해주었다. 이후, 직사각형 4개의 각 변들과 선분과의 CCW >0 이면 선분이 직사각형 내부에 있다는 뜻이므로 이 또한 T로 판별하게 해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 .. # BOJ 2162번: 선분 그룹 2차원 평면상에 선분들이 주어질 때, 두 선분이 만나면 같은 그룹이라 한다. 이때 가장 큰 그룹에 속한 선분의 개수를 구하는 문제이다. 그룹핑하기 위해 Union Find를 사용했고, CCW로 선분의 교차 유무를 판별하였다. 코드는 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 #include #include int p.. 이전 1 다음