test/aoj/2308.test.cpp

View this file on GitHub
Last update: 2020-10-27 15:50:08+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2308

Depends on

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2308

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

#define call_from_test
#include "../../tools/chminmax.cpp"
#include "../../tools/drop.cpp"
#include "../../io/precision.cpp"
#include "../../geometry/projectilemotion.cpp"
#undef call_from_test

using D = double;
struct Point{
  D x,y;
  Point(){}
  Point(D x,D y):x(x),y(y){}
};

istream &operator>>(istream &is,Point &p){
  is>>p.x>>p.y;
  return is;
}

signed main(){
  int n;
  D v;
  cin>>n>>v;
  Point t;
  cin>>t;
  vector<Point> ps(n),qs(n);
  for(int i=0;i<n;i++) cin>>ps[i]>>qs[i];
  for(int i=0;i<n;i++) chmin(qs[i].x,t.x);

  D g=9.8;

  if(t.x==0){
    D ti=v/g;
    D y=v*ti-g/2*ti*ti;
    if(y>=t.y) drop("Yes");
    drop("No");
  }

  const D EPS = 1e-10;
  vector<D> cand;
  auto push=
    [&](Point s){
      for(auto pq:projectile_motion(v,g,s.x,s.y)){
        D d=pq.first;
        cand.emplace_back(d);
        cand.emplace_back(d+EPS);
        cand.emplace_back(d-EPS);
      }
    };

  for(int i=0;i<n;i++){
    if(ps[i].x>=t.x) continue;
    push(ps[i]);
    push(qs[i]);
    push(Point(ps[i].x,qs[i].y));
    push(Point(qs[i].x,ps[i].y));
  }
  push(t);

  auto getY=
    [&](D p,D q,D x){
      D ti=x/p;
      return q*ti-g/2*ti*ti;
    };

  auto in=
    [&](int k,D p,D q)->int{
      if(ps[k].x>=t.x) return 0;

      if(ps[k].y<getY(p,q,ps[k].x) && getY(p,q,ps[k].x)<qs[k].y) return 1;
      if(ps[k].y<getY(p,q,qs[k].x) && getY(p,q,qs[k].x)<qs[k].y) return 1;

      if(ps[k].y<getY(p,q,ps[k].x) && getY(p,q,qs[k].x)<ps[k].y) return 1;
      if(ps[k].y<getY(p,q,qs[k].x) && getY(p,q,ps[k].x)<ps[k].y) return 1;

      if(qs[k].y<getY(p,q,ps[k].x) && getY(p,q,qs[k].x)<qs[k].y) return 1;
      if(qs[k].y<getY(p,q,qs[k].x) && getY(p,q,ps[k].x)<qs[k].y) return 1;

      D ti=q/g;
      Point top(p*ti,getY(p,q,p*ti));
      if(ps[k].x<top.x && top.x<qs[k].x &&
         ps[k].y<top.y && top.y<qs[k].y) return 1;

      return 0;
    };


  for(D p:cand){
    D q=sqrt(v*v-p*p);

    if(getY(p,q,t.x)<t.y) continue;

    int flg=1;
    for(int i=0;i<n;i++)
      if(in(i,p,q)) flg=0;

    if(flg) drop("Yes");
  }

  cout<<"No"<<endl;
  return 0;
}

#line 1 "test/aoj/2308.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2308

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

#define call_from_test
#line 1 "tools/chminmax.cpp"

#line 3 "tools/chminmax.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "tools/drop.cpp"

#line 3 "tools/drop.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 1 "io/precision.cpp"

#line 3 "io/precision.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
struct Precision{
  Precision(){
    cout<<fixed<<setprecision(12);
  }
}precision_beet;
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "geometry/projectilemotion.cpp"

#line 3 "geometry/projectilemotion.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// throw from origin to (x,y) with verocity v (x>0)
// g: gravity
template<typename D>
vector< pair<D, D> > projectile_motion(D v,D g,D x,D y){
  D a=x*x+y*y;
  D b=g*x*x*y-v*v*x*x;
  D c=g*g*x*x*x*x/4;
  if(b*b<4*a*c) return {};
  vector< pair<D, D> > res;
  {
    D p=(-b+sqrt(b*b-4*a*c))/(2*a);
    if(0<p and p<v*v) res.emplace_back(sqrt(p),sqrt(v*v-p));
  }
  {
    D p=(-b-sqrt(b*b-4*a*c))/(2*a);
    if(0<p and p<v*v) res.emplace_back(sqrt(p),sqrt(v*v-p));
  }
  return res;
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 11 "test/aoj/2308.test.cpp"
#undef call_from_test

using D = double;
struct Point{
  D x,y;
  Point(){}
  Point(D x,D y):x(x),y(y){}
};

istream &operator>>(istream &is,Point &p){
  is>>p.x>>p.y;
  return is;
}

signed main(){
  int n;
  D v;
  cin>>n>>v;
  Point t;
  cin>>t;
  vector<Point> ps(n),qs(n);
  for(int i=0;i<n;i++) cin>>ps[i]>>qs[i];
  for(int i=0;i<n;i++) chmin(qs[i].x,t.x);

  D g=9.8;

  if(t.x==0){
    D ti=v/g;
    D y=v*ti-g/2*ti*ti;
    if(y>=t.y) drop("Yes");
    drop("No");
  }

  const D EPS = 1e-10;
  vector<D> cand;
  auto push=
    [&](Point s){
      for(auto pq:projectile_motion(v,g,s.x,s.y)){
        D d=pq.first;
        cand.emplace_back(d);
        cand.emplace_back(d+EPS);
        cand.emplace_back(d-EPS);
      }
    };

  for(int i=0;i<n;i++){
    if(ps[i].x>=t.x) continue;
    push(ps[i]);
    push(qs[i]);
    push(Point(ps[i].x,qs[i].y));
    push(Point(qs[i].x,ps[i].y));
  }
  push(t);

  auto getY=
    [&](D p,D q,D x){
      D ti=x/p;
      return q*ti-g/2*ti*ti;
    };

  auto in=
    [&](int k,D p,D q)->int{
      if(ps[k].x>=t.x) return 0;

      if(ps[k].y<getY(p,q,ps[k].x) && getY(p,q,ps[k].x)<qs[k].y) return 1;
      if(ps[k].y<getY(p,q,qs[k].x) && getY(p,q,qs[k].x)<qs[k].y) return 1;

      if(ps[k].y<getY(p,q,ps[k].x) && getY(p,q,qs[k].x)<ps[k].y) return 1;
      if(ps[k].y<getY(p,q,qs[k].x) && getY(p,q,ps[k].x)<ps[k].y) return 1;

      if(qs[k].y<getY(p,q,ps[k].x) && getY(p,q,qs[k].x)<qs[k].y) return 1;
      if(qs[k].y<getY(p,q,qs[k].x) && getY(p,q,ps[k].x)<qs[k].y) return 1;

      D ti=q/g;
      Point top(p*ti,getY(p,q,p*ti));
      if(ps[k].x<top.x && top.x<qs[k].x &&
         ps[k].y<top.y && top.y<qs[k].y) return 1;

      return 0;
    };


  for(D p:cand){
    D q=sqrt(v*v-p*p);

    if(getY(p,q,t.x)<t.y) continue;

    int flg=1;
    for(int i=0;i<n;i++)
      if(in(i,p,q)) flg=0;

    if(flg) drop("Yes");
  }

  cout<<"No"<<endl;
  return 0;
}