[백준 알고리즘] Node.js 1485. 정사각형 만들기
2023. 12. 7. 13:41ㆍ코딩연습
1. 문제
https://www.acmicpc.net/problem/1485
1485번: 정사각형
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 네 줄로 이루어져 있으며, 점의 좌표가 한 줄에 하나씩 주어진다. 점의 좌표는 -100,000보다 크거나 같고, 100,000보다 작거나 같
www.acmicpc.net
2. 풀이
- 질문게시판에 있는 풀이를 참고하였다.
- 중심으로부터 각 점까지의 길이가 모두 동일한 지 확인하고,
- 중심을 원점으로 이동시키면서 각 점도 중심이 원점으로 이동한 만큼 이동시킨다.
- 이동한 점들을 90도 회전시키고, 이 회전 시킨 점들이 2번에 있는 점들과 동일하다면 정사각형이 된다.
const inputs = require('fs').readFileSync('/dev/stdin').toString().trim()
.toString().trim().split('\n');
const T = +inputs.shift();
let res = ""
// 거리 계산을 위한 함수.
const CalsDistance = (a,b) => {
const [x1,y1] = a;
const [x2,y2] = b;
return Math.pow(Math.pow((x2-x1), 2) + Math.pow((y2-y1), 2), 0.5);
}
for(let i = 0; i < T; i++){
// 4개씩 끊어서 케이스가 주어짐.
const cases = inputs.slice(4*i, 4*i+4).map(v => v.split(" ").map(vv => +vv));
// x의 값을 먼저 오름차순 정렬하고, 이후 y의 값을 오름차순 정렬.
cases.sort((a,b) => {
if(a[0] < b[0]) return -1;
else if(a[0] > b[0]) return 1;
else {
if(a[1] < b[1]) return -1
else if(a[1] > b[1]) return 1;
else return 0;
}
})
// 네 점의 중심점 구하기.
const mid = cases.reduce((acc, cur) => {
acc[0] += cur[0]
acc[1] += cur[1]
return acc;
}, [0,0]).map(v => v/4)
// 중심점과의 거리 구하기.
const fromMidDis = [];
for(let j = 0; j < 4; j++){
fromMidDis.push(CalsDistance(mid, cases[j]))
}
// 중심점과의 거리가 다르다면 정사각형이 아니므로 0.
const fromMidDisUnique = new Set([...fromMidDis]);
if(fromMidDisUnique.size !== 1) res += '0\n';
else { // 거리가 같다면 90도 회전시켜서 정사각형인지 확인.
// 원점을 중심으로 옮기기.
const newCases = cases.map(v => {
return [v[0] - mid[0], v[1] - mid[1]]
})
// 각 점을 90도 회전.
const rotation = Array.from({length : 4}, () => []);
for(let j = 0; j < 4; j++){
rotation[j] = [(-1)*newCases[j][1], newCases[j][0]]
}
// 90도 회전시킨 점이 원점을 중심으로 옮겼을 때의 점들과 동일한 지 확인.
const checking = rotation.map(rot => {
// 만약 회전시킨 점이 없다면 false, 있다면 true 리턴.
if(newCases.findIndex((item) => item[0] === rot[0] && item[1] === rot[1]) === -1) {
return false;
} else return true;
})
// 하나라도 false가 있다면 정사각형이 아니므로 0
if(checking.includes(false)) res += '0\n';
else res += '1\n'
}
}
console.log(res)
3. 정리
- 처음엔 ' ㅁ ' 이렇게 생긴 정사각형만 생각해서 x1 === x2 && y1 === y2 와 같은 방식으로 지정했었다. 그리고 각 변의 길이가 동일하면 되겠지 라고 단순하게 생각했다. 그러다 질문게시판을 보고 마름모 형태의 정사각형이 있다는 사실도 알게 되었고, 점들이 모두 다르지만 정사각형인 경우등 되게 다양하다는 사실을 깨닫게 되었다.
- 그래서 정사각형이 될 조건을 생각해서 각도로 문제를 풀어보려다가 sin, cos에 정신이 나갈뻔했다. 다행히(?) 중간점을 이용해서 푸신 분 덕에 문제를 해결할 수 있었다. 이게 python인지 C++인지는 모르겟지만 보고 해석하는데 조금 시간이 걸렸다. 질문 게시판의 ' ggodong ' 님 감사합니다. 감사합니다.
'코딩연습' 카테고리의 다른 글
[백준 알고리즘] Node.js 2167. 2차원 배열의 합 (0) | 2023.12.18 |
---|---|
[백준 알고리즘] Node.js 2057. 팩토리얼 분해 (1) | 2023.12.11 |
[백준 알고리즘] Node.js 1448. 삼각형 만들기 (2) | 2023.12.05 |
[백준 알고리즘] Node.js 1021. 회전하는 큐 (1) | 2023.11.29 |
[백준 알고리즘] Node.js 1246. 온라인 판매 (0) | 2023.11.27 |