AtCoder Beginner Contest #010 C問題 - 浮気調査

Source

AtCoder Beginner Contest #010
問題文

問題概要

高橋くんは，時間 $0$ に二次元平面上の座標 $(X_a, Y_a)$ にいて，時間 $T$ には座標 $(X_b, Y_b)$ にいたことがわかっている．
高橋くんは，最大で速さ $V$ で動くことができる．
また，$N$ 人の女の子の家の座標 $(X_k, Y_k), \;\; k=1,2,\ldots,N$ が与えられる．
高橋くんは，時刻 $0$ と $T$ の間にどこかの女の子の家に寄った可能性があるかどうかを判定する問題．
与えられるデータは矛盾はない（$(X_a,Y_a)$ から $(X_b,Y_b)$ に時刻 $T$ までに移動可能である）ことは保証されている．

解法

$(X_a, Y_a)$ と $(X_k,Y_k)$ 間の距離と $(X_b, Y_b)$ と $(X_k,Y_k)$ 間の距離の和が $TV$ 以下となるような $k$ が存在するか調べる．
$(a,b)$ と $(c,d)$ の間の距離は $\sqrt{(a-c)^2 + (b-d)^2}$ で計算できる．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define EPS 1e-9

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}

double dist(double dx, double dy){ return sqrt(dx*dx+dy*dy); }

int SX, SY, EX, EY, T, V;
int N, X, Y;

int main(){
  int i, j, k;
  int res = 0;

  reader(&SX,&SY);
  reader(&EX,&EY);
  reader(&T,&V);
  reader(&N);
  while(N--){
    reader(&X,&Y);
    if(T*V > dist(SX-X,SY-Y) + dist(EX-X,EY-Y) - EPS) res++;
  }

  if(res) writer("YES\n"); else writer("NO\n");

  return 0;
}

Current time: 2024年04月19日20時53分16秒
Last modified: 2014年06月26日21時29分07秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Beginner_Contest ABC010 ABC_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：