1119-Exploring Caves
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1119
問題概要
ロボットが(0,0)からx>=0,y>=0を常に満たすように移動する。
そのロボットが到達した位置で最も遠くかつxが最も大きい所を求めよ。
ただしロボットの移動はdx,dyで与えられ、dx*dy=0を満たす。
dx==0&&dy==0の時は一つの入力の最後となる。
考え方
シュミレートする
実装(C++)
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <climits> #include <cctype> #include <ctime> #include <cassert> #include <cwchar> #include <cstdarg> #include <cwctype> #include <queue> #include <stack> #include <algorithm> #include <list> #include <vector> #include <set> #include <map> #include <iostream> #include <deque> #include <complex> #include <string> #include <functional> #include <iomanip> #include <sstream> using namespace std; typedef long long int lli; typedef unsigned int uint; int main(){ int N; scanf("%d",&N); int x,y; int dx,dy; int resx,resy,resv; for(int i=0;i<N;i++){ resv=0; x=0,y=0; do{ scanf("%d%d",&dx,&dy); if(dx==0&&dy==0)break; x+=dx;y+=dy; if(x*x+y*y>resv){ resv=x*x+y*y; resx=x;resy=y; } else if(resv==x*x+y*y){ if(x>resx){ resx=x; resy=y; } } }while(1); printf("%d %d\n",resx,resy); } return 0; }