구슬 (BEAD)
| 시간 제한 | 메모리 제한 |
| 2 초 | 512 MB |
문제
물리를 사랑하는 민준이는 집에 마찰이 없는 무한한 수직선과 완전탄성충돌을 하고 질량이 동일하며 크기를 무시할 수 있는 구슬 N(1 ≤ N ≤100,000)개를 구비해놓고 있다. 어느 날 민준이는 모션캡처분석기기를 활용하기 위해 N개의 구슬 중 하나만 빨간색으로 색칠한 뒤 실을 연결해 N중 진자 실험을 하고 있었다. 이를 해석역학적으로 분석하며, r과 θ의 관계를 파악하던 중 구슬의 질량에 의한 장력을 이기지 못한 실들이 한 번에 끊어져 수직선 위에 널부러지게 되었다. 각각 다른 위치 xi에 떨어져 저마다의 초속도 vi를 가지고 운동하게 된 구슬을 보며 민준이는 가슴 아파 했지만 곧 새로운 물리 문제를 떠올리는 데에 성공한다! 바로 t(1 ≤ t ≤109)초 후 빨간 구슬의 위치를 구하는 것이다! 하지만 민준이는 지나치게 많은 구슬의 양에 그만 t초 동안 정신을 잃고 말았다. 민준이가 깨기 전에 답을 구해 민준이를 행복하게 해 주자!
입력
첫째 줄에 구슬의 개수 N과 시간 t가 주어진다.
둘째 줄부터 N개의 줄에는 xi와 vi가 주어진다. (-109 ≤ xi, vi ≤ 109)
단, 빨간 구슬은 입력에서 첫 번째로 주어지는 구슬이며, v가 음수인 경우는 –x방향으로 진행함을 의미한다.
주어지는 모든 수는 정수이다.
출력
t 초 후 빨간 구슬의 위치를 출력한다. 이 값이 정수임은 보장된다.
예제 입력 1
4 3
5 -4
3 3
-2 5
7 112힌트
2/7초 후 빨간 구슬이 2번 구슬과 충돌한 뒤 2초 후 4번 구슬과 충돌하고 5/2초 후 다시 2번 구슬과 충돌해 3초 후에는 12의 위치에 있게 된다.
완전탄성충돌이란 운동량과 운동에너지 모두 보존되는 충돌을 의미한다.
https://youtu.be/4YeMJHz6xG0?t=212
https://domaindeveloper.tistory.com/48
(완전 탄성 충돌, 비탄성 충돌, 완전 비탄성 충돌)
위 3가지 충돌에 대해 알기 위해 반발 계수라는 것을 먼저 알아야 한다. 반발계수(e) : 두 물체가 충돌하기 전 두 물체의 상대 속도에 대한 충돌한 후 상대 속도의 비. 즉, 두 물체에서, 충돌전 상
domaindeveloper.tistory.com
https://ko.wikipedia.org/wiki/%ED%83%84%EC%84%B1_%EC%B6%A9%EB%8F%8C
탄성 충돌 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 열교란 상태의 원자는 흑체 복사가 계에서 방출되지 않는 동안 기본적으로 탄성 충돌을 한다. 대체로 두 원자가 되튈 때는 충돌 전과 같은 운동 에너지를 가진
ko.wikipedia.org
질량이 같은 물체의 완전 탄성충돌은 서로의 속도를 교환한다. 뉴턴의 요람처럼 충돌시 정지한 구슬이 움직이고 움직이던 구슬이 정지한다. 마치 영혼이 바뀌는 것 처럼. 에너지의 손실이 없는 완전 탄성충돌에다가 구체의 지름을 고려하지 않아도 되기 때문에 아무런 충돌이 없이 서로 지나친다고 가정했을 때의 t초 후의 위치에 bead가 위치하게 된다.
하지만 서로 순서가 바뀔 수 없다. 충돌이 없다고 가정한 t초 후의 위치를 계산하고 원래의 빨간 공의 순서에 있는 수직선상의 위치가 바로 빨간 공의 위치가 된다.
def s():
n,t,x,v,*r=map(int,open(0).read().split())
order_red=0
pos_future=[x+v*t]
for i in range(0,(n-1)<<1,2):
order_red+=(x>r[i])
pos_future.append(r[i]+r[i+1]*t)
pos_future.sort()
print(pos_future[order_red])
s()공의 개수 시간 초기위치와 속도를 받고 나머지 위치 속도를 한 번에 받은 뒤
빨간 공보다 앞서는 좌표를 세면서 나머지 공들의 t초 후의 위치를 추가해주고
정렬해서 처음 빨간 공과 같은 순서의 위치가 바로 t초 후 빨간 공의 위치다.
import React, { useState, useEffect, useRef } from 'react';
import { Slider } from '@/components/ui/slider';
import { Button } from '@/components/ui/button';
import { Play, Pause, RefreshCw } from 'lucide-react';
const BeadCollision = () => {
const [time, setTime] = useState(0);
const [isPlaying, setIsPlaying] = useState(false);
const animationRef = useRef();
const lastUpdateRef = useRef(Date.now());
const initialState = [
{ x: 5, v: -4, number: 1 },
{ x: 3, v: 3, number: 2 },
{ x: -2, v: 5, number: 3 },
{ x: 7, v: 1, number: 4 }
];
const findNextCollision = (beads, startTime) => {
let minTime = Infinity;
let collisionPair = null;
// 모든 구슬 쌍을 검사
for (let i = 0; i < beads.length; i++) {
for (let j = i + 1; j < beads.length; j++) {
const b1 = beads[i];
const b2 = beads[j];
// 상대 속도가 0이면 충돌하지 않음
if (b1.v === b2.v) continue;
// 충돌 시간 계산
const t = -(b1.x - b2.x) / (b1.v - b2.v);
// 양수이고 현재까지 찾은 최소 시간보다 작은 경우만 고려
if (t > 0 && t < minTime) {
// 충돌 위치 계산
const x1 = b1.x + b1.v * t;
const x2 = b2.x + b2.v * t;
// 위치가 정확히 일치하는지 확인
if (Math.abs(x1 - x2) < 0.000001) {
minTime = t;
collisionPair = [i, j];
}
}
}
}
return minTime === Infinity ? null : {
time: startTime + minTime,
beads: collisionPair
};
};
const calculatePositions = (targetTime) => {
let currentTime = 0;
let beads = [...initialState];
let collisions = [];
while (true) {
const nextCollision = findNextCollision(beads, currentTime);
if (!nextCollision || nextCollision.time > targetTime) break;
// 충돌 순간까지 위치 이동
beads = beads.map(bead => ({
...bead,
x: bead.x + bead.v * (nextCollision.time - currentTime)
}));
const [i, j] = nextCollision.beads;
// 번호만 교환하여 시각적인 충돌 효과 생성
const tempNumber = beads[i].number;
beads[i].number = beads[j].number;
beads[j].number = tempNumber;
// 속도도 교환
const tempV = beads[i].v;
beads[i].v = beads[j].v;
beads[j].v = tempV;
collisions.push({
...nextCollision,
time: nextCollision.time,
bead1: beads[i].number,
bead2: beads[j].number
});
currentTime = nextCollision.time;
}
beads = beads.map(bead => ({
...bead,
x: bead.x + bead.v * (targetTime - currentTime)
}));
return { beads, collisions };
};
useEffect(() => {
if (isPlaying && time < 3) {
const animate = () => {
const now = Date.now();
const deltaTime = (now - lastUpdateRef.current) / 1000 * 0.05;
lastUpdateRef.current = now;
setTime(prevTime => {
const newTime = prevTime + deltaTime;
return newTime <= 3 ? newTime : 3;
});
animationRef.current = requestAnimationFrame(animate);
};
lastUpdateRef.current = Date.now();
animationRef.current = requestAnimationFrame(animate);
return () => {
if (animationRef.current) {
cancelAnimationFrame(animationRef.current);
}
};
}
}, [isPlaying, time]);
const { beads, collisions } = calculatePositions(time);
// x 좌표로 정렬하여 첫 번째 구슬을 빨간색으로 표시
const sortedBeads = [...beads].sort((a, b) => a.x - b.x);
const togglePlay = () => {
if (!isPlaying) {
lastUpdateRef.current = Date.now();
}
setIsPlaying(!isPlaying);
};
const reset = () => {
setTime(0);
setIsPlaying(false);
};
const ticks = Array.from({ length: 21 }, (_, i) => i - 10);
return (
<div className="w-full p-4">
<div className="mb-4 flex items-center gap-4">
<Button onClick={togglePlay} variant="outline" size="icon">
{isPlaying ? <Pause className="h-4 w-4" /> : <Play className="h-4 w-4" />}
</Button>
<Button onClick={reset} variant="outline" size="icon">
<RefreshCw className="h-4 w-4" />
</Button>
<div className="flex-grow">
<p className="text-sm mb-2">Time: {time.toFixed(3)}s</p>
<Slider
min={0}
max={3}
step={0.001}
value={[time]}
onValueChange={(value) => {
setTime(value[0]);
setIsPlaying(false);
}}
/>
</div>
</div>
<div className="relative h-32 bg-gray-100 rounded-lg">
<div className="absolute left-0 right-0 top-1/2 h-px bg-gray-300" />
{ticks.map((tick) => (
<div
key={tick}
className="absolute top-1/2 w-px h-2 bg-gray-400"
style={{
left: `${((tick + 10) / 20) * 100}%`,
transform: 'translateY(-50%)'
}}
>
<span className="absolute top-4 left-1/2 transform -translate-x-1/2 text-xs">
{tick}
</span>
</div>
))}
{sortedBeads.map((bead, index) => {
const xPos = ((bead.x + 10) / 20) * 100;
// index + 1이 위치 순서(rank)가 됩니다
return (
<div key={bead.x} className="relative">
<div
className={`absolute top-1/2 -translate-y-1/2 w-4 h-4 rounded-full
${index === 2 ? 'bg-red-500' : 'bg-blue-500'}`}
style={{
left: `${Math.max(0, Math.min(100, xPos))}%`
}}
/>
<div
className="absolute text-xs font-bold"
style={{
left: `${Math.max(0, Math.min(100, xPos))}%`,
top: '50%',
transform: 'translate(-50%, -150%)'
}}
>
{index + 1}
</div>
</div>
);
})}
</div>
<div className="mt-4 text-sm space-y-1">
<p>Red bead position: {sortedBeads[2].x.toFixed(3)}</p>
<p>Red bead velocity: {sortedBeads[2].v.toFixed(3)}</p>
<p>Collisions: {collisions.length > 0 ?
collisions.map(c => `t=${c.time.toFixed(3)}s [${c.bead1},${c.bead2}]`).join(', ') :
'None yet'}</p>
</div>
</div>
);
};
export default BeadCollision;