fork download
copy 
  1. #include<cassert>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<vector>
  5. #include<tuple>
  6. using namespace std;
  7.  
  8. #ifndef M_PI
  9. const double M_PI = acos(-1);
  10. #endif
  11. const double eps=1e-10, fps=10, dt=1/fps;
  12. int sgn(double c){
  13.     return (c>eps)-(c<-eps);
  14. }
  15.  
  16. #define NP 25 // maximum number of platforms
  17. int np; // number of platforms
  18. double py[NP], pl[NP], pr[NP]; // y-coordinates, left x-coordinates, right x-coordinates of platforms
  19.  
  20. #define NM 25 // maximum number of monsters
  21. struct point{
  22.     double x, y;
  23.     point(double x=0, double y=0): x(x), y(y){}
  24.     point operator +(const point &q) const{
  25.         return point(x+q.x, y+q.y);
  26.     }
  27.     point operator -() const{
  28.         return point(-x, -y);
  29.     }
  30.     point operator -(const point &q) const{
  31.         return (*this)+(-q);
  32.     }
  33.     point operator *(const double &c) const{
  34.         return point(c*x, c*y);
  35.     }
  36.     double len() const{
  37.         return hypot(x, y);
  38.     }
  39. };
  40. point operator *(const double &c, const point &p){
  41.     return p*c;
  42. }
  43. int nm; // number of monsters
  44. bool mt[NM]; // monster type, 0 for SHM, 1 for circular motion
  45. point mp0[NM], mp1[NM]; // p0: initial position (SHM) or center (circular motion), p1: farthest position (SHM only)
  46. double momega[NM], mr[NM]; // omega: angular velocity, r: radius (circular motion only)
  47. point mp(int i, double t){ // monster i's position at time t
  48.     if(mt[i]){
  49.         return mp0[i] + mr[i]*point(cos(momega[i]*t), sin(momega[i]*t));
  50.     }else{
  51.         return .5*(mp0[i]+mp1[i]) + .5*(mp0[i]-mp1[i])*cos(momega[i]*t);
  52.     }
  53. }
  54.  
  55. #define L 10000
  56. char str[L]; // input string composed of commands
  57. struct state{
  58.     point p, v; // p: position, v: velocity
  59.     int pno; // 0: aloft; otherwise: platform no.
  60.     state(const point &p=point(), const point &v=point(), const int &pno=0): p(p), v(v), pno(pno){}
  61. };
  62. pair<int, double> loli(const state &s){ // return what platform the player jumps to and how long it takes to reach that platform
  63.     if(s.pno){
  64.         return make_pair(s.pno, 0.);
  65.     }
  66.     double x0=s.p.x, y0=s.p.y, vx=s.v.x, vy=s.v.y;
  67.     if(sgn(vx) == 0){
  68.         double h = y0;
  69.         if(sgn(vy) >= 0) h += vy*vy/4;
  70.         int no = 0;
  71.         for(int i=1; i<=np; i++) if(sgn(x0-pl[i])>=0 && sgn(pr[i]-x0)>=0 && sgn(h-py[i])>=0){
  72.             if(!no || sgn(py[i]-py[no])>0){
  73.                 no = i;
  74.             }
  75.         }
  76.         assert(no);
  77.         if(sgn(vy)<0) h += vy*vy/4;
  78.         h -= py[no];
  79.         if(sgn(h)==0) h = 0;
  80.         return make_pair(no, sqrt(h)+vy/2);
  81.     }
  82.     double a=-1/(vx*vx), b=vy/vx+2*x0/(vx*vx), c=y0-vy*x0/vx-x0*x0/(vx*vx); // y=ax^2+bx+c
  83.     int no = 0;
  84.     double time;
  85.     for(int i=1; i<=np; i++){
  86.         double D = b*b-4*a*(c-py[i]);
  87.         if(sgn(D)<0) continue;
  88.         if(sgn(D)==0) D = 0;
  89.         double xt;
  90.         if(sgn(vx)>0) xt=(-b-sqrt(D))/(2*a);
  91.         else xt=(-b+sqrt(D))/(2*a);
  92.         double t = (xt-x0)/vx;
  93.         if(sgn(xt-pl[i])>=0 && sgn(pr[i]-xt)>=0 && sgn(t)>0){
  94.             if(!no || sgn(time-t)>0){
  95.                 no=i, time=t;
  96.             }
  97.         }
  98.     }
  99.     assert(no);
  100.     return make_pair(no, time);
  101. }
  102. state ugoku(const state &s, double t){ // the command and s.pno are not allowed to change in the following t seconds
  103.     if(s.pno){
  104.         return state(s.p+s.v*t, s.v, s.pno);
  105.     }else{
  106.         return state(s.p+s.v*t-point(0, t*t), s.v-point(0, 2*t), s.pno);
  107.     }
  108. }
  109.  
  110. int main(){
  111.     scanf("%d", &np);
  112.     for(int i=1; i<=np; i++){
  113.         scanf("%lf%lf%lf", py+i, pl+i, pr+i);
  114.     }
  115.     scanf("%d", &nm);
  116.     for(int i=1; i<=nm; i++){
  117.         char t;
  118.         scanf(" %c", &t);
  119.         double T;
  120.         if(t == 'h'){
  121.             mt[i] = 0;
  122.             scanf("%lf%lf%lf%lf%lf", &mp0[i].x, &mp0[i].y, &mp1[i].x, &mp1[i].y, &T);
  123.         }else{
  124.             mt[i] = 1;
  125.             scanf("%lf%lf%lf%lf", &mp0[i].x, &mp0[i].y, mr+i, &T);
  126.         }
  127.         momega[i] = 2*M_PI/T;
  128.     }
  129.     point start;
  130.     int T;
  131.     scanf("%lf%lf%d", &start.x, &start.y, &T);
  132.     fgets(str, L, stdin);
  133.     vector<state> traj(1, state(start)); // trajectory
  134.     for(int i=1; i<=np; i++){
  135.         if(sgn(start.y-py[i])==0 && sgn(start.x-pl[i])>=0 && sgn(pr[i]-start.x)>=0){
  136.             traj[0].pno = i; break;
  137.         }
  138.     }
  139.     while(T--){
  140.         fgets(str, L, stdin);
  141.         int offset=0, delta;
  142.         char cmd[10];
  143.         double tc;
  144.         state s = traj[0];
  145.         for(; ~sscanf(str+offset, "%s%lf%n", cmd, &tc, &delta); offset+=delta){
  146.             int cnt = round(fps*tc);
  147.             assert(sgn(cnt-fps*tc) == 0);
  148.             if(cmd[0]=='n'){
  149.                 int no; double tr; // tr: reach a platform
  150.                 tie(no, tr) = loli(s);
  151.                 if(sgn(tr)==0){
  152.                     s.v = point();
  153.                     s.pno = no;
  154.                 }
  155.                 while(cnt--){
  156.                     if(sgn(tr-dt)>0){
  157.                         s = ugoku(s, dt);
  158.                         tr -= dt;
  159.                     }else if(sgn(tr)>0){
  160.                         s = ugoku(s, tr);
  161.                         s.v = point();
  162.                         s.pno = no;
  163.                         tr = 0;
  164.                     }
  165.                     traj.push_back(s);
  166.                 }
  167.             }else if(cmd[0]=='l' && cmd[1]=='w'){
  168.                 int no; double tr, tl=0, tt=dt; // tl: leave a platform, tt: next tick
  169.                 tie(no, tr) = loli(s);
  170.                 if(sgn(tr)==0){
  171.                     s.v = point(-1, 0);
  172.                     s.pno = no;
  173.                     tl = s.p.x-pl[no];
  174.                 }
  175.                 while(cnt){
  176.                     if(sgn(tr-tt)>0){
  177.                         s = ugoku(s, tt);
  178.                         traj.push_back(s);
  179.                         tr-=tt; tt=dt; cnt--;
  180.                     }else if(sgn(tr)>0){
  181.                         s = ugoku(s, tr);
  182.                         s.v = point(-1, 0);
  183.                         s.pno = no;
  184.                         tt-=tr; tr=0; tl=s.p.x-pl[no];
  185.                         if(sgn(tt)==0){
  186.                             traj.push_back(s);
  187.                             tt=dt; cnt--;
  188.                         }
  189.                     }else if(sgn(tl-tt)>0){
  190.                         s = ugoku(s, tt);
  191.                         traj.push_back(s);
  192.                         tl-=tt; tt=dt; cnt--;
  193.                     }else{
  194.                         s = ugoku(s, tl);
  195.                         s.pno = 0;
  196.                         tt-=tl; tl=0; tie(no, tr)=loli(s);
  197.                         if(sgn(tt)==0){
  198.                             traj.push_back(s);
  199.                             tt=dt; cnt--;
  200.                         }
  201.                     }
  202.                 }
  203.             }else if(cmd[0]=='r' && cmd[1]=='w'){
  204.                 int no; double tr, tl=0, tt=dt;
  205.                 tie(no, tr) = loli(s);
  206.                 if(sgn(tr)==0){
  207.                     s.v = point(1, 0);
  208.                     s.pno = no;
  209.                     tl = pr[no]-s.p.x;
  210.                 }
  211.                 while(cnt){
  212.                     if(sgn(tr-tt)>0){
  213.                         s = ugoku(s, tt);
  214.                         traj.push_back(s);
  215.                         tr-=tt; tt=dt; cnt--;
  216.                     }else if(sgn(tr)>0){
  217.                         s = ugoku(s, tr);
  218.                         s.v = point(1, 0);
  219.                         s.pno = no;
  220.                         tt-=tr; tr=0; tl=pr[no]-s.p.x;
  221.                         if(sgn(tt)==0){
  222.                             traj.push_back(s);
  223.                             tt=dt; cnt--;
  224.                         }
  225.                     }else if(sgn(tl-tt)>0){
  226.                         s = ugoku(s, tt);
  227.                         traj.push_back(s);
  228.                         tl-=tt; tt=dt; cnt--;
  229.                     }else{
  230.                         s = ugoku(s, tl);
  231.                         s.pno = 0;
  232.                         tt-=tl; tl=0; tie(no, tr)=loli(s);
  233.                         if(sgn(tt)==0){
  234.                             traj.push_back(s);
  235.                             tt=dt; cnt--;
  236.                         }
  237.                     }
  238.                 }
  239.             }else if(cmd[0]=='u'){
  240.                 int no; double tr, tt=dt;
  241.                 tie(no, tr) = loli(s);
  242.                 while(cnt){
  243.                     if(sgn(tr-tt)>0){
  244.                         s = ugoku(s, tt);
  245.                         traj.push_back(s);
  246.                         tr-=tt; tt=dt; cnt--;
  247.                     }else if(sgn(tr)>0){
  248.                         s = ugoku(s, tr);
  249.                         s.v = point(0, 2);
  250.                         tt-=tr; tie(no, tr)=loli(s);
  251.                         if(sgn(tt)==0){
  252.                             traj.push_back(s);
  253.                             tt=dt; cnt--;
  254.                         }
  255.                     }else{
  256.                         s.v = point(0, 2);
  257.                         s.pno = 0;
  258.                         tie(no, tr) = loli(s);
  259.                     }
  260.                 }
  261.             }else if(cmd[0]=='l' && cmd[1]=='j'){
  262.                 int no; double tr, tt=dt;
  263.                 tie(no, tr) = loli(s);
  264.                 while(cnt){
  265.                     if(sgn(tr-tt)>0){
  266.                         s = ugoku(s, tt);
  267.                         traj.push_back(s);
  268.                         tr-=tt; tt=dt; cnt--;
  269.                     }else if(sgn(tr)>0){
  270.                         s = ugoku(s, tr);
  271.                         s.v = point(-sqrt(2), sqrt(2));
  272.                         tt-=tr; tie(no, tr)=loli(s);
  273.                         if(sgn(tt)==0){
  274.                             traj.push_back(s);
  275.                             tt=dt; cnt--;
  276.                         }
  277.                     }else{
  278.                         s.v = point(-sqrt(2), sqrt(2));
  279.                         s.pno = 0;
  280.                         tie(no, tr) = loli(s);
  281.                     }
  282.                 }
  283.             }else{
  284.                 int no; double tr, tt=dt;
  285.                 tie(no, tr) = loli(s);
  286.                 while(cnt){
  287.                     if(sgn(tr-tt)>0){
  288.                         s = ugoku(s, tt);
  289.                         traj.push_back(s);
  290.                         tr-=tt; tt=dt; cnt--;
  291.                     }else if(sgn(tr)>0){
  292.                         s = ugoku(s, tr);
  293.                         s.v = point(sqrt(2), sqrt(2));
  294.                         tt-=tr; tie(no, tr)=loli(s);
  295.                         if(sgn(tt)==0){
  296.                             traj.push_back(s);
  297.                             tt=dt; cnt--;
  298.                         }
  299.                     }else{
  300.                         s.v = point(sqrt(2), sqrt(2));
  301.                         s.pno = 0;
  302.                         tie(no, tr) = loli(s);
  303.                     }
  304.                 }
  305.             }
  306.         }
  307.         int no; double tr;
  308.         tie(no, tr) = loli(s);
  309.         if(sgn(tr)==0){
  310.             s.v = point();
  311.             s.pno = no;
  312.         }
  313.         while(sgn(tr)>0){
  314.             if(sgn(tr-dt)>0){
  315.                 s = ugoku(s, dt);
  316.                 tr -= dt;
  317.             }else if(sgn(tr)>0){
  318.                 s = ugoku(s, tr);
  319.                 s.v = point();
  320.                 s.pno = no;
  321.                 tr = 0;
  322.             }
  323.             traj.push_back(s);
  324.         }
  325.         for(int i=1; i<=fps; i++){
  326.             traj.push_back(s);
  327.         }
  328.         bool win = true;
  329.         for(int i=0; i<(int)traj.size(); i++){
  330.             for(int j=1; j<=nm; j++){
  331.                 if(sgn((traj[i].p-mp(j, i*dt)).len()-.5) < 0){
  332.                     win = false; break;
  333.                 }
  334.             }
  335.             if(!win){
  336.                 break;
  337.             }
  338.         }
  339.         printf("%c\n", "NY"[win]);
  340.         traj.resize(1);
  341.     }
  342.     return 0;
  343. }
  344.  
Success #stdin #stdout 0s 4496KB
comments (?)
stdin
copy 
2
0 0 4
0 5 8
2
h 100 100 200 200 1
h 1.5 -1 1.5 1 4
0.5 0.0001
2
rwalk 3 rjump 0.1 rwalk 1
none 1 rwalk 3 rjump 0.1 rwalk 1
stdout
copy 
N
Y
https://ideone.com/2JKbzD
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!