Yandex.Algorithm 2015 Round 2.2 A問題 - Odysseus Sails Home

Source

Yandex.Algorithm 2015
Yandex.Algorithm 2015 Round 2.2
問題文

問題概要

$2$ 次元平面上に無限に広がる海を考える.
今,自分の船は,座標 $(S_X,S_Y)$ にいて,座標 $(T_X,T_Y)$ に辿り着くことが目標である.
最初は無風だが,風を吹かせる魔法の書を持っていて,$N$ 種類の風を吹かせることができ,風 $k$ が吹いているときは,速度 $(X_k, Y_k)$ で船は進む.
それぞれの風は好きなときに好きなだけ吹かせることができる.
目的地にたどり着けるかどうかを判定する問題.

解法

現在地を原点にし,$(T_X-S_X,T_Y-S_Y)$ に移動したいとする.
$2$ つの風を使えば,その風が同じ方向かちょうど逆向きでなければ,その間の方向は全て辿り着くことができる.
よって,$3$ つ以上の風を使う必要はない.
まず,目的地が原点の場合は,風を使うまでもなく辿りつけているので,その場合を処理する.
目的地と全く同じ方角の風がある場合は,辿り着けるとする.
また,全ての $2$ つの風の組み合わせを試し,その $2$ つの風の方向の中に目的地の方向があればたどり着けるとする.
これは,風のベクトルを $a,b$ とし,目的地のベクトルを $t$ としたとき,$a$ からみて $b,t$ が左右同じ方にあり,$b$ からみても $a,t$ が左右同じ方にあるということである.
よって,同じ方向かどうかも含めて,全て符号付き三角形の面積を求めてやることで整数演算で行うことができる(実数で行うと誤差が厳しい).
無風の風の存在に注意する.

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 ll long long

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);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

int SX, SY, GX, GY;
int N;
int DX[111], DY[111];

ll dir(ll x1, ll y1, ll x2, ll y2){
  return x1 * y2 - x2 * y1;
}

int main(){
  int i, j;
  int ok = 0;
  ll s1, s2;

  reader(&SX,&SY);
  reader(&GX,&GY);
  reader(&N);
  rep(i,N) reader(DX+i,DY+i);

  GX -= SX;
  GY -= SY;
  if(GX==0 && GY==0){ writerLn("YES"); return 0; }

  rep(i,N){
    if(dir(GX, GY, DX[i], DY[i])==0){
      if(GX){
        s1 = GX;
        s2 = DX[i];
      } else {
        s1 = GY;
        s2 = DY[i];
      }
      if(s1 <= 0 && s2 >= 0) continue;
      if(s1 >= 0 && s2 <= 0) continue;
      ok = 1;
    }
  }

  rep(i,N) rep(j,N) if(i!=j){
    s1 = dir(DX[i],DY[i],GX,GY);
    s2 = dir(DX[i],DY[i],DX[j],DY[j]);
    if(s1 >= 0 && s2 <= 0) continue;
    if(s1 <= 0 && s2 >= 0) continue;
    s1 = dir(DX[j],DY[j],GX,GY);
    s2 = dir(DX[j],DY[j],DX[i],DY[i]);
    if(s1 >= 0 && s2 <= 0) continue;
    if(s1 <= 0 && s2 >= 0) continue;
    ok = 1;
  }

  if(ok) writerLn("YES"); else writerLn("NO");

  return 0;
}

Current time: 2017年07月23日15時33分35秒
Last modified: 2015年06月28日03時30分15秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2015 Yandex_Algorithm_2015_Round22
トップページに戻る

Logged in as: unknown user (not login)

ログイン: