BOJ 34965 자기장 측정기

문제 링크입니다.

문제 요약

좌표평면 위를 각 축에 평행하게 움직이는 점의 자취가 주어집니다.

자취 중 원점으로부터의 거리가 최소인 지점을 찾으세요.

풀이

축평행 선분 위의 점 중 원점에 가장 가까운 점은 수직인 축과 만나는 점, 그러한 점이 없으면 양 끝점 중 원점에 더 가까운 점입니다.

그냥 그대로 구현하면 됩니다. 오버플로우 또는 실수 오차에 유의합니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using lll = __int128;
using pll = pair<ll, ll>;
 
const int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
const lll INF = LLONG_MAX;
lll dist(lll x, lll y){
    if(x < 0) x = -x; if(y < 0) y = -y;
    if(x > 2'000'000'000LL || y > 2'000'000'000LL) return INF;
    return x*x+y*y;
}
 
int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	ll sx, sy; cin >> sx >> sy; if(!sx && !sy) return !(cout << -1);
	lll x = -sx, y = -sy;
	lll ax = x, ay = y;
	string s; cin >> s; int parser = 0; int dir = 0;
	while(parser < s.size()){
		char op = s[parser++];
		int d = 0;
		while(isdigit(s[parser])) d = d*10+s[parser++]-'0';
		if(op == 'S'){ //go
			lll nx = x+d*dx[dir], ny = y+d*dy[dir];
			if(x*nx <= 0 && y*ny <= 0) return !(cout << -1);
			if(dist(nx, ny) < dist(ax, ay)) ax = nx, ay = ny;
			if(x*nx < 0) if(dist(0, y) < dist(ax, ay)) ax = 0, ay = y;
			if(y*ny < 0) if(dist(x, 0) < dist(ax, ay)) ax = x, ay = 0;
			x = nx; y = ny;
		}
		if(op == 'T'){ //rot
			dir += d; dir %= 4;
		}
	}
	cout << (ll)(ax+sx) << ' ' << (ll)(ay+sy);
}