Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

RAIC 2012 Mr.Smile v90

a guest Dec 2nd, 2012 3,627 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. #include "MyStrategy.h"
  2.  
  3. #define _USE_MATH_DEFINES
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <limits>
  8. #include <algorithm>
  9. #include <list>
  10. #include <map>
  11.  
  12. #include <iostream>  // DEBUG
  13. #include <iomanip>  // DEBUG
  14. #include <ctime>  // DEBUG
  15.  
  16. using namespace model;
  17. using namespace std;
  18.  
  19.  
  20.  
  21. inline double sqr(double x)
  22. {
  23.     return x * x;
  24. }
  25.  
  26. inline double rem(double x, double y)
  27. {
  28.     x /= y;  return y * (x - floor(x));
  29. }
  30.  
  31.  
  32. struct Vec2D
  33. {
  34.     double x, y;
  35.  
  36.     Vec2D()
  37.     {
  38.     }
  39.  
  40.     Vec2D(const Vec2D &v) : x(v.x), y(v.y)
  41.     {
  42.     }
  43.  
  44.     Vec2D(double x_, double y_) : x(x_), y(y_)
  45.     {
  46.     }
  47.  
  48.     Vec2D &operator = (const Vec2D &v)
  49.     {
  50.         x = v.x;  y = v.y;  return *this;
  51.     }
  52.  
  53.     Vec2D operator + (const Vec2D &v) const
  54.     {
  55.         return Vec2D(x + v.x, y + v.y);
  56.     }
  57.  
  58.     Vec2D &operator += (const Vec2D &v)
  59.     {
  60.         x += v.x;  y += v.y;  return *this;
  61.     }
  62.  
  63.     Vec2D operator - (const Vec2D &v) const
  64.     {
  65.         return Vec2D(x - v.x, y - v.y);
  66.     }
  67.  
  68.     Vec2D &operator -= (const Vec2D &v)
  69.     {
  70.         x -= v.x;  y -= v.y;  return *this;
  71.     }
  72.  
  73.     Vec2D operator - () const
  74.     {
  75.         return Vec2D(-x, -y);
  76.     }
  77.  
  78.     Vec2D operator * (double a) const
  79.     {
  80.         return Vec2D(a * x, a * y);
  81.     }
  82.  
  83.     Vec2D &operator *= (double a)
  84.     {
  85.         x *= a;  y *= a;  return *this;
  86.     }
  87.  
  88.     double operator * (const Vec2D &v) const
  89.     {
  90.         return x * v.x + y * v.y;
  91.     }
  92.  
  93.     Vec2D operator / (double a) const
  94.     {
  95.         return (*this) * (1 / a);
  96.     }
  97.  
  98.     Vec2D operator /= (double a)
  99.     {
  100.         return (*this) *= (1 / a);
  101.     }
  102.  
  103.     Vec2D operator ~ () const
  104.     {
  105.         return Vec2D(y, -x);
  106.     }
  107.  
  108.     double operator % (const Vec2D &v) const
  109.     {
  110.         return *this * ~v;
  111.     }
  112.  
  113.     double sqr() const
  114.     {
  115.         return x * x + y * y;
  116.     }
  117.  
  118.     double len() const
  119.     {
  120.         return std::sqrt(x * x + y * y);
  121.     }
  122. };
  123.  
  124. inline Vec2D operator * (double a, const Vec2D &v)
  125. {
  126.     return v * a;
  127. }
  128.  
  129. inline Vec2D normalize(const Vec2D &v)
  130. {
  131.     return v / v.len();
  132. }
  133.  
  134. inline Vec2D sincos(double angle)
  135. {
  136.     return Vec2D(cos(angle), sin(angle));
  137. }
  138.  
  139. inline Vec2D conj(const Vec2D &v)
  140. {
  141.     return Vec2D(v.x, -v.y);
  142. }
  143.  
  144.  
  145. struct Quad
  146. {
  147.     Vec2D pos, dir;
  148.     double half_w, half_h;
  149.  
  150.     Quad()
  151.     {
  152.     }
  153.  
  154.     Quad(const Vec2D &pos_, const Vec2D &dir_, double hw, double hh) :
  155.         pos(pos_), dir(dir_), half_w(hw), half_h(hh)
  156.     {
  157.     }
  158.  
  159.     Quad(const Unit &unit) : pos(unit.x(), unit.y()),
  160.         dir(sincos(unit.angle())), half_w(unit.width() / 2), half_h(unit.height() / 2)
  161.     {
  162.     }
  163.  
  164.     Quad(const Vec2D &start, const Vec2D &delta, double size) : half_h(size / 2)
  165.     {
  166.         dir = delta / 2;  half_w = dir.len();  pos = start + dir;  dir /= half_w;
  167.     }
  168.  
  169.     Quad move(const Vec2D &pt) const
  170.     {
  171.         return Quad(pt, dir, half_w, half_h);
  172.     }
  173.  
  174.     bool checkPoint(const Vec2D &pt, double rad = 0) const
  175.     {
  176.         Vec2D dr = pt - pos;
  177.         return abs(dr * dir) < half_w + rad && abs(dr % dir) < half_h + rad;
  178.     }
  179.  
  180.     bool cross(const Quad &q) const
  181.     {
  182.         Vec2D dr = pos - q.pos;
  183.         //if(dr.sqr() > sqr(half_w + half_h + q.half_w + q.half_h))return false;
  184.  
  185.         double dot = abs(dir * q.dir), cross = abs(dir % q.dir);
  186.         if(!(abs(dr * dir) < half_w + q.half_w * dot + q.half_h * cross))return false;
  187.         if(!(abs(dr % dir) < half_h + q.half_h * dot + q.half_w * cross))return false;
  188.         if(!(abs(dr * q.dir) < q.half_w + half_w * dot + half_h * cross))return false;
  189.         if(!(abs(dr % q.dir) < q.half_h + half_h * dot + half_w * cross))return false;
  190.         return true;
  191.     }
  192.  
  193.     void crossRange(const Quad &q, const Vec2D &delta, double &t_min, double &t_max) const
  194.     {
  195.         Vec2D dr = pos - q.pos;
  196.         double center1 = dr * dir, center2 = dr % dir;
  197.         double center3 = dr * q.dir, center4 = dr % q.dir;
  198.         double dot = abs(dir * q.dir), cross = abs(dir % q.dir);
  199.         double delta1 = half_w + q.half_w * dot + q.half_h * cross;
  200.         double delta2 = half_h + q.half_h * dot + q.half_w * cross;
  201.         double delta3 = q.half_w + half_w * dot + half_h * cross;
  202.         double delta4 = q.half_h + half_h * dot + half_w * cross;
  203.  
  204.         double mul1 = 1 / (delta * dir), mul2 = 1 / (delta % dir);
  205.         double mul3 = 1 / (delta * q.dir), mul4 = 1 / (delta % q.dir);
  206.         if(mul1 < 0)delta1 = -delta1;  if(mul2 < 0)delta2 = -delta2;
  207.         if(mul3 < 0)delta3 = -delta3;  if(mul4 < 0)delta4 = -delta4;
  208.         t_min = max(max((center1 - delta1) * mul1, (center2 - delta2) * mul2),
  209.                     max((center3 - delta3) * mul3, (center4 - delta4) * mul4));
  210.         t_max = min(min((center1 + delta1) * mul1, (center2 + delta2) * mul2),
  211.                     min((center3 + delta3) * mul3, (center4 + delta4) * mul4));
  212.     }
  213.  
  214.     void crossLine(const Vec2D &start, const Vec2D &delta, double &t_min, double &t_max) const
  215.     {
  216.         Vec2D dr = pos - start;
  217.         double center1 = dr * dir, center2 = dr % dir;
  218.         double delta1 = half_w, delta2 = half_h;
  219.  
  220.         double mul1 = 1 / (delta * dir), mul2 = 1 / (delta % dir);
  221.         if(mul1 < 0)delta1 = -delta1;  if(mul2 < 0)delta2 = -delta2;
  222.         t_min = max((center1 - delta1) * mul1, (center2 - delta2) * mul2);
  223.         t_max = min((center1 + delta1) * mul1, (center2 + delta2) * mul2);
  224.     }
  225. };
  226.  
  227.  
  228.  
  229. struct GlobalParams
  230. {
  231.     double crew_danger_att, hull_danger_att, ang_spd_account;
  232.     double medkit_score, repkit_score, ammo_score;
  233.     double obst_danger, phys_lookahead, rot_bonus;
  234.     double tg_border, tg_lookahead;
  235.     double tg_prem_danger, tg_ang_att, tg_base_score;
  236.     double tg_prem_bonus, tg_prem_offs, tg_fire_thr;
  237.     double aggr_factor, aggr_lookahead;
  238.     double team_force, team_dist;
  239.     double dng_ang_att, dng_lookahead;
  240.     double prem_danger, hit_danger;
  241.  
  242. #ifdef OPTIMIZING
  243.  
  244.     GlobalParams()
  245.     {
  246.         static const unsigned long long flag = 0x0123456789ABCDEF;
  247.  
  248.         unsigned long long buf;
  249.         cin.read(reinterpret_cast<char *>(&buf), sizeof(buf));
  250.         if(buf == flag)
  251.         {
  252.             cin.read(reinterpret_cast<char *>(this), sizeof(*this));
  253.             cin.read(reinterpret_cast<char *>(&buf), sizeof(buf));
  254.             if(buf == flag)return;
  255.         }
  256.         cout << "Invalid input!!!" << endl;  exit(-1);
  257.     }
  258.  
  259. #else
  260.  
  261.     GlobalParams()
  262.     {
  263.         /*crew_danger_att = 0.4;
  264.         hull_danger_att = 0.3;
  265.         ang_spd_account = 0.1;
  266.         medkit_score = 2.5;
  267.         repkit_score = 0.4;
  268.         ammo_score = 0.2;
  269.         obst_danger = 30;
  270.         phys_lookahead = 50;
  271.         rot_bonus = 10;
  272.         tg_border = 8;
  273.         tg_lookahead = 600;
  274.         tg_prem_danger = 0;
  275.         tg_ang_att = 0.07;
  276.         tg_base_score = 0.8;
  277.         tg_prem_bonus = 3;
  278.         tg_prem_offs = 2;
  279.         tg_fire_thr = 0.25;
  280.         aggr_factor = 1.2;
  281.         aggr_lookahead = 30000;
  282.         team_force = 0.08;
  283.         team_dist = 250;
  284.         dng_ang_att = 6;
  285.         dng_lookahead = 100;
  286.         prem_danger = 0.5;
  287.         hit_danger = 4000;*/
  288.  
  289.         /*crew_danger_att = 0.7;
  290.         hull_danger_att = 0.15;
  291.         ang_spd_account = 0.5;
  292.         medkit_score = 5;
  293.         repkit_score = 0.3;
  294.         ammo_score = 1;
  295.         obst_danger = 8;
  296.         phys_lookahead = 70;
  297.         rot_bonus = 2;
  298.         tg_border = 8;
  299.         tg_lookahead = 200;
  300.         tg_prem_danger = 0.04;
  301.         tg_ang_att = 0.01;
  302.         tg_base_score = 1;
  303.         tg_prem_bonus = 20;
  304.         tg_prem_offs = 10;
  305.         tg_fire_thr = 0.3;
  306.         aggr_factor = 0.2;
  307.         aggr_lookahead = 2000;
  308.         team_force = 0.08;
  309.         team_dist = 200;
  310.         dng_ang_att = 20;
  311.         dng_lookahead = 50;
  312.         prem_danger = 0.1;
  313.         hit_danger = 200;*/
  314.  
  315.         crew_danger_att = 0.7;
  316.         hull_danger_att = 0.15;
  317.         ang_spd_account = 0.5;
  318.         medkit_score = 5;
  319.         repkit_score = 0.3;
  320.         ammo_score = 1;
  321.         obst_danger = 8;
  322.         phys_lookahead = 70;
  323.         rot_bonus = 2;
  324.         tg_border = 8;
  325.         tg_lookahead = 200;
  326.         tg_prem_danger = 0.04;
  327.         tg_ang_att = 0.01;
  328.         tg_base_score = 1;
  329.         tg_prem_bonus = 20;
  330.         tg_prem_offs = 10;
  331.         tg_fire_thr = 0.3;
  332.         aggr_factor = 2;
  333.         aggr_lookahead = 2000;
  334.         team_force = 0.08;
  335.         team_dist = 200;
  336.         dng_ang_att = 20;
  337.         dng_lookahead = 50;
  338.         prem_danger = 0.1;
  339.         hit_danger = 200;
  340.     }
  341.  
  342. #endif
  343.  
  344. };
  345.  
  346. const GlobalParams prm;
  347.  
  348.  
  349.  
  350. struct ShellInfo
  351. {
  352.     double frict, v0, mul, range, score;
  353.     FireType fire;
  354.  
  355.     ShellInfo(double frict_, double v0_, FireType fire_, double score_) :
  356.         frict(frict_), v0(v0_), mul(1 / log(1 - frict_)), range(v0_ / frict_), score(score_), fire(fire_)
  357.     {
  358.     }
  359. };
  360.  
  361. const ShellInfo shell_info[] =
  362. {
  363.     ShellInfo(0.005, 50 / 3.0, REGULAR_FIRE, 10),
  364.     ShellInfo(0.010, 40 / 3.0, PREMIUM_FIRE, 20)
  365. };
  366.  
  367.  
  368.  
  369. inline double crew_danger(const Tank &tank)
  370. {
  371.     return 1 - prm.crew_danger_att * tank.crew_health() / tank.crew_max_health();
  372. }
  373.  
  374. inline double hull_danger(const Tank &tank)
  375. {
  376.     return 1 - prm.hull_danger_att * tank.hull_durability() / tank.hull_max_durability();
  377. }
  378.  
  379. struct FriendRef
  380. {
  381.     Vec2D pos, turret;
  382.     double ang_spd, gun_len, gun_angle;
  383.     double danger;  bool premium;  size_t quad_index;
  384.     long long id;  int prev_dir;
  385.  
  386.     FriendRef(const Tank &tank, size_t index, int prev) : pos(tank.x(), tank.y()),
  387.         ang_spd(tank.angular_speed()), gun_len(tank.virtual_gun_length()),
  388.         gun_angle(tank.angle() + tank.turret_relative_angle()),
  389.         danger(max(crew_danger(tank), hull_danger(tank))),
  390.         premium(tank.premium_shell_count()), quad_index(index),
  391.         id(tank.id()), prev_dir(prev)
  392.     {
  393.         turret = sincos(gun_angle);
  394.     }
  395. };
  396.  
  397.  
  398. struct BonusRef
  399. {
  400.     Vec2D pos;
  401.     BonusType type;
  402.  
  403.     static void calcScore(const Tank &tank, double score[3])
  404.     {
  405.         score[MEDIKIT] = prm.medkit_score * crew_danger(tank) *
  406.             min(1.0, (tank.crew_max_health() - tank.crew_health()) / 35.0);
  407.         score[REPAIR_KIT] = prm.repkit_score * hull_danger(tank) *
  408.             min(1.0, (tank.hull_max_durability() - tank.hull_durability()) / 50.0);
  409.         score[AMMO_CRATE] = prm.ammo_score;
  410.     }
  411.  
  412.     BonusRef(const Bonus &bonus) : pos(bonus.x(), bonus.y()), type(bonus.type())
  413.     {
  414.     }
  415. };
  416.  
  417.  
  418. struct Action
  419. {
  420.     double force, moment;
  421.  
  422.     Action()
  423.     {
  424.     }
  425.  
  426.     Action(const Tank &tank, double move_l, double move_r)
  427.     {
  428.         if(move_l < 0)move_l *= tank.engine_rear_power_factor();
  429.         if(move_r < 0)move_r *= tank.engine_rear_power_factor();
  430.         double mul = 0.04947917 * (1 + tank.crew_health() / double(tank.crew_max_health()));
  431.         force = (move_l + move_r) * mul;  moment = 0.004229904 * (move_l - move_r) * mul;
  432.     }
  433. };
  434.  
  435. struct State : public Quad
  436. {
  437.     double angle, ang_spd;
  438.     Vec2D spd;
  439.  
  440.     State()
  441.     {
  442.     }
  443.  
  444.     State(const Unit &unit) : Quad(unit),
  445.         angle(unit.angle()), ang_spd(unit.angular_speed()),
  446.         spd(unit.speed_x(), unit.speed_y())
  447.     {
  448.     }
  449.  
  450.     void bounce(const Vec2D &r, const Vec2D &norm, double depth)
  451.     {
  452.         double rt = r % norm, ri = rt / 975, w = 1 / (1 + rt * ri);
  453.         double pr = -1.325 * min(0.0, spd * norm + 0.51 * rt * ang_spd) * w;
  454.         double pp = 0.8 * max(0.0, depth - 0.01) * w;
  455.         spd += pr * norm;  ang_spd += pr * ri;
  456.         pos += pp * norm;  angle += pp * ri;
  457.     }
  458.  
  459.     void checkBounds(const Vec2D &size)
  460.     {
  461.         double w = size.x / 2, h = size.y / 2;
  462.         Vec2D rw = half_w * dir, rh = half_h * ~dir;
  463.         Vec2D r1 = rw + rh, r2 = rw - rh;
  464.  
  465.         double depth = abs(pos.x - w) + max(abs(r1.x), abs(r2.x)) - w;
  466.         if(depth > 0)
  467.         {
  468.             Vec2D norm(pos.x < w ? 1 : -1, 0);
  469.             Vec2D &r = abs(r1.x) > abs(r2.x) ? r1 : r2;
  470.             bounce((r.x < 0 ? norm.x : -norm.x) * r, norm, depth);
  471.         }
  472.         depth = abs(pos.y - h) + max(abs(r1.y), abs(r2.y)) - h;
  473.         if(depth > 0)
  474.         {
  475.             Vec2D norm(0, pos.y < h ? 1 : -1);
  476.             Vec2D &r = abs(r1.y) > abs(r2.y) ? r1 : r2;
  477.             bounce((r.y < 0 ? norm.y : -norm.y) * r, norm, depth);
  478.         }
  479.     }
  480.  
  481.     void advance(const Action &act, const Vec2D &size)
  482.     {
  483.         spd += act.force * dir - 0.05 * spd;
  484.         ang_spd += act.moment - 0.02051282 * ang_spd;
  485.  
  486.         checkBounds(size);
  487.         pos += spd;  dir = sincos(angle += ang_spd);
  488.     }
  489. };
  490.  
  491.  
  492. struct ShellRef : public Quad
  493. {
  494.     Vec2D spd;
  495.     double frict, score;
  496.  
  497.     ShellRef()
  498.     {
  499.     }
  500.  
  501.     ShellRef(const Vec2D &pos, const Vec2D &dir, double gun_len, ShellType type) :
  502.         Quad(pos + dir * gun_len, dir, 11.25, 3.75), spd(shell_info[type].v0 * dir),
  503.         frict(shell_info[type].frict), score(shell_info[type].score)
  504.  
  505.     {
  506.     }
  507.  
  508.     ShellRef(const Shell &shell) : Quad(shell), spd(shell.speed_x(), shell.speed_y()),
  509.         frict(shell_info[shell.type()].frict), score(shell_info[shell.type()].score)
  510.     {
  511.     }
  512.  
  513.     void advance()
  514.     {
  515.         spd -= frict * spd;  pos += spd;
  516.     }
  517. };
  518.  
  519.  
  520. struct TankInfo
  521. {
  522.     double force, moment, damp, rot_damp;
  523.  
  524.     TankInfo(double force_, double moment_, double damp_, double rot_damp_) :
  525.         force(force_), moment(moment_), damp(damp_), rot_damp(rot_damp_)
  526.     {
  527.     }
  528. };
  529.  
  530. const TankInfo tank_info[] =
  531. {
  532.     TankInfo(0.19791669, 0.00020929222, 1.0 / 20, 0.02051282),  // MEDIUM
  533.     TankInfo(0.11510416, 0.00008385862, 1.0 / 40, 0.01441441),  // HEAVY
  534.     TankInfo(0.08950617, 0.00006365248, 1.0 / 30, 0.01394335)   // TANK_DESTROYER
  535. };
  536.  
  537.  
  538. struct ScoreElem
  539. {
  540.     double pos, val;
  541.  
  542.     ScoreElem()
  543.     {
  544.     }
  545.  
  546.     ScoreElem(double pos_, double val_) : pos(pos_), val(val_)
  547.     {
  548.     }
  549. };
  550.  
  551. struct ScoreRange : public list<ScoreElem>
  552. {
  553.     ScoreRange()
  554.     {
  555.         push_back(ScoreElem(-numeric_limits<double>::infinity(), 0));
  556.         push_back(ScoreElem(numeric_limits<double>::infinity(), 0));
  557.     }
  558.  
  559.     static double timeMerge(double prev, double cur)
  560.     {
  561.         return prev == 0 ? cur : prev;
  562.     }
  563.  
  564.     static double addMerge(double prev, double cur)
  565.     {
  566.         return prev + cur;
  567.     }
  568.  
  569.     template<double (*func)(double, double), typename Iter> void merge(Iter beg, Iter end)
  570.     {
  571.         iterator ptr = begin();
  572.         double prev = 0, cur = 0, res = 0;  ++ptr;
  573.         for(; beg != end; ++beg)
  574.         {
  575.             while(ptr->pos < beg->pos)
  576.             {
  577.                 double val = func(prev = ptr->val, cur);
  578.                 iterator old = ptr++;
  579.                 if(val == res)erase(old);
  580.                 else old->val = res = val;
  581.             }
  582.             cur = beg->val;
  583.             if(ptr->pos == beg->pos)
  584.             {
  585.                 double val = func(prev = ptr->val, cur);
  586.                 iterator old = ptr++;
  587.                 if(val == res)erase(old);
  588.                 else old->val = res = val;
  589.             }
  590.             else
  591.             {
  592.                 double val = func(prev, cur);
  593.                 if(val != res)insert(ptr, ScoreElem(beg->pos, res = val));
  594.             }
  595.         }
  596.     }
  597.  
  598.     void merge(ScoreElem *elem, size_t n)
  599.     {
  600.         merge<timeMerge>(elem, elem + n);
  601.     }
  602.  
  603.     void add(const ScoreRange &rng)
  604.     {
  605.         const_iterator first = rng.begin(), last = rng.end();
  606.         if(++first != --last)merge<addMerge>(first, last);
  607.     }
  608.  
  609.     double integrate() const
  610.     {
  611.         const_iterator ptr = begin(), last = end();  if(++ptr == --last)return 0;
  612.         for(double res = 0;;)
  613.         {
  614.             const_iterator old = ptr;  if(++ptr == last)return res;
  615.             res += sqrt(sqrt(old->val)) * (ptr->pos - old->pos);
  616.         }
  617.     }
  618.  
  619.     void print() const
  620.     {
  621.         const_iterator ptr = begin(), last = end();  cout << ptr->val;
  622.         for(++ptr, --last; ptr != last; ++ptr)cout << " (" << ptr->pos << ") " << ptr->val;
  623.         cout << endl;
  624.     }
  625. };
  626.  
  627.  
  628. struct Target
  629. {
  630.     struct Prediction
  631.     {
  632.         Vec2D pos, delta, dir;
  633.         double min, max;
  634.     };
  635.  
  636.  
  637.     static const int max_pred = 256;
  638.     static const double dmul;
  639.  
  640.  
  641.     double half_w, half_h;
  642.     vector<Prediction> pred;
  643.     double delta_min, delta_max;
  644.     ScoreRange base_range;
  645.     double score_offset;
  646.  
  647.     Vec2D turret;
  648.     double gun_len, score_mul;
  649.     int fire_time;  bool premium;
  650.     size_t quad_index;
  651.  
  652.     Target(const Tank &tank, size_t index) :
  653.         half_w(tank.width() / 2 - prm.tg_border),
  654.         half_h(tank.height() / 2 - prm.tg_border),
  655.         turret(sincos(tank.angle() + tank.turret_relative_angle())),
  656.         gun_len(tank.virtual_gun_length()),
  657.         score_mul(sqr(max(crew_danger(tank), hull_danger(tank)))),
  658.         fire_time(tank.remaining_reloading_time()),
  659.         premium(tank.premium_shell_count()), quad_index(index)
  660.     {
  661.     }
  662.  
  663.     void generate(const Tank &tank);
  664.     void calcRange(ShellRef shell, int step, int total, ScoreRange &range) const;
  665.  
  666.     void processShell(const ShellRef &shell)
  667.     {
  668.         ScoreRange range;  calcRange(shell, 0, max_pred, range);  base_range.add(range);
  669.     }
  670.  
  671.     void updateBase()
  672.     {
  673.         score_offset = sqr(sqr(base_range.integrate() / (delta_max - delta_min)));
  674.     }
  675.  
  676.     double calcScore(const ShellRef &shell, int step, int total) const
  677.     {
  678.         ScoreRange range;  calcRange(shell, step, total, range);  range.add(base_range);
  679.         return sqr(sqr(range.integrate() / (delta_max - delta_min))) - score_offset;
  680.     }
  681. };
  682.  
  683. const double Target::dmul = exp(-1 / prm.tg_lookahead);
  684.  
  685.  
  686. struct GunMove
  687. {
  688.     double gun_move;
  689.     FireType fire_type;
  690. };
  691.  
  692. struct DangerField
  693. {
  694.     static const double h, dmul, max_bonus;
  695.  
  696.     static int cur_tick;
  697.     static vector<Target> target;
  698.     static vector<FriendRef> fref;
  699.     static vector<ShellRef> sref;
  700.     static vector<Vec2D> shell_pos;
  701.     static vector<BonusRef> bref;
  702.     static vector<Quad> quad;
  703.     static size_t block_count;
  704.  
  705.     static Vec2D size, offset;
  706.     static size_t width, height;
  707.  
  708.  
  709.     size_t cur, quad_index;
  710.     vector<double> danger;
  711.     double min_danger;
  712.  
  713.     vector<Action> act;
  714.     double bonus_score[3];
  715.     double tg_angle, gun_spd;
  716.     int fire_time;
  717.  
  718.     double gun_spd_p, gun_spd_n, gun_move;
  719.     FireType fire_type;
  720.  
  721.  
  722.     static void init(const World &world);
  723.     DangerField(const World &world, const Tank &tank);
  724.  
  725.     static bool checkRay(const Vec2D &start, const Vec2D &delta, size_t skip1, size_t skip2 = -1);
  726.     static double checkRay(const ShellRef &shell, size_t skip1, size_t skip2 = -1);
  727.     void blur();
  728.  
  729.     double sampleDanger(const Vec2D &pos);
  730.     double hitDanger(const State &state, size_t index, int step);
  731.     double samplePhys(State state, size_t index, const size_t *max_act,
  732.         double mul, double sum, vector<bool> flag, double best, int step = 0);
  733.     size_t samplePhys(const Tank &tank, const double move[][2], const size_t *max_move);
  734.     double checkTarget(const Target &tank, double angle, double &best_angle, GunMove &res, double best);
  735.  
  736.     void print();
  737. };
  738.  
  739. const double DangerField::h = 16;  // blur() dependent
  740. const double DangerField::dmul = exp(-1 / prm.phys_lookahead);
  741. const double DangerField::max_bonus = prm.medkit_score + prm.repkit_score + prm.ammo_score;
  742.  
  743. int DangerField::cur_tick = -1;
  744. vector<Target> DangerField::target;
  745. vector<FriendRef> DangerField::fref;
  746. vector<ShellRef> DangerField::sref;
  747. vector<Vec2D> DangerField::shell_pos;
  748. vector<BonusRef> DangerField::bref;
  749. vector<Quad> DangerField::quad;
  750. size_t DangerField::block_count;
  751.  
  752. Vec2D DangerField::size, DangerField::offset;
  753. size_t DangerField::width, DangerField::height;
  754.  
  755.  
  756. inline double shellFlyTime(double dist, ShellType type)
  757. {
  758.     if(!(dist < shell_info[type].range))return numeric_limits<double>::infinity();
  759.     return shell_info[type].mul * log(1 - dist / shell_info[type].range);
  760. }
  761.  
  762. void DangerField::init(const World &world)
  763. {
  764.     if(world.tick() == cur_tick)return;
  765.     //cout << cur_tick << endl;
  766.     cur_tick = world.tick();
  767.  
  768.     size = Vec2D(world.width(), world.height());
  769.     width = size_t(floor(size.x / h + 0.5)) + 6;
  770.     height = size_t(floor(size.y / h + 0.5)) + 6;
  771.     offset = (size - Vec2D(width - 1, height - 1) * h) / 2;
  772.  
  773.     vector<Tank> tanks = world.tanks();
  774.     vector<Shell> shells = world.shells();
  775.     vector<Bonus> bonuses = world.bonuses();
  776.     vector<Obstacle> obstacles = world.obstacles();
  777.  
  778.     quad.clear();
  779.     for(vector<Obstacle>::iterator ptr = obstacles.begin(); ptr != obstacles.end(); ++ptr)
  780.         quad.push_back(*ptr);
  781.  
  782.     map<long long, int> prev_dir;
  783.     for(vector<FriendRef>::iterator ptr = fref.begin(); ptr != fref.end(); ++ptr)
  784.         prev_dir[ptr->id] = ptr->prev_dir;
  785.  
  786.     target.clear();  fref.clear();
  787.     for(vector<Tank>::iterator ptr = tanks.begin(); ptr != tanks.end(); ++ptr)
  788.     {
  789.         if(ptr->crew_health() && ptr->hull_durability())
  790.             if(ptr->teammate())fref.push_back(FriendRef(*ptr, quad.size(), prev_dir[ptr->id()]));
  791.             else target.push_back(Target(*ptr, quad.size()));
  792.         quad.push_back(*ptr);
  793.     }
  794.     block_count = quad.size();
  795.  
  796.     sref.clear();  shell_pos.clear();
  797.     for(vector<Shell>::iterator ptr = shells.begin(); ptr != shells.end(); ++ptr)
  798.     {
  799.         sref.push_back(*ptr);  shell_pos.push_back(sref[sref.size() - 1].pos);
  800.     }
  801.  
  802.     bref.clear();
  803.     for(vector<Bonus>::iterator ptr = bonuses.begin(); ptr != bonuses.end(); ++ptr)
  804.     {
  805.         quad.push_back(*ptr);  bref.push_back(*ptr);
  806.     }
  807.  
  808.     size_t index = 0;
  809.     for(vector<Tank>::iterator ptr = tanks.begin(); ptr != tanks.end(); ++ptr)
  810.         if(!ptr->teammate() && ptr->crew_health() && ptr->hull_durability())
  811.             target[index++].generate(*ptr);
  812.  
  813.     for(size_t i = 0; i < target.size(); i++)
  814.     {
  815.         double mul = 0;
  816.         for(size_t j = 0; j < fref.size(); j++)
  817.         {
  818.             Vec2D delta = target[i].pred[0].pos - fref[j].pos;
  819.             double dist = delta.len(), cos_turret = target[i].turret * delta / dist;
  820.  
  821.             double val = 1 - dist / shell_info[REGULAR].range;
  822.             if(target[i].premium)val = max(val, (prm.tg_prem_danger + 1) * (1 - dist / shell_info[PREMIUM].range));
  823.             val *= exp(-prm.tg_ang_att * (1 + cos_turret)) * fref[j].danger;  mul = max(mul, val);
  824.         }
  825.         target[i].score_mul *= mul + prm.tg_base_score;
  826.  
  827.         for(size_t j = 0; j < sref.size(); j++)target[i].processShell(sref[j]);
  828.         target[i].updateBase();
  829.     }
  830. }
  831.  
  832. DangerField::DangerField(const World &world, const Tank &tank) : gun_move(0), fire_type(NONE)
  833. {
  834.     init(world);
  835.     for(cur = 0;; cur++)
  836.         if(cur >= fref.size())
  837.         {
  838.             cur = -1;  return;
  839.         }
  840.         else if(fref[cur].id == tank.id())break;
  841.     quad_index = fref[cur].quad_index;
  842.  
  843.     danger.resize(width * height);  vector<double> aggr(width * height);
  844.  
  845.     fire_time = tank.remaining_reloading_time();
  846.     double aggr_mul = prm.aggr_factor * exp(-fire_time / prm.aggr_lookahead) * fref.size() / target.size();
  847.     for(size_t j = 0, k = 0; j < height; j++)for(size_t i = 0; i < width; i++, k++)
  848.     {
  849.         Vec2D start = offset + Vec2D(i, j) * h;
  850.         if(!(start.x > 0 && start.x < size.x && start.y > 0 && start.y < size.y))
  851.         {
  852.             danger[k] = prm.obst_danger;  continue;
  853.         }
  854.  
  855.         for(size_t i = 0; i < block_count; i++)
  856.             if(i != quad_index && quad[i].checkPoint(start))
  857.             {
  858.                 danger[k] += prm.obst_danger;  break;
  859.             }
  860.  
  861.         for(size_t i = 0; i < fref.size(); i++)if(i != cur)
  862.             danger[k] += prm.team_force * sqr(2 / (1 + (fref[i].pos - start).sqr() / sqr(prm.team_dist)) - 1);
  863.  
  864.         for(vector<Target>::iterator ptr = target.begin(); ptr != target.end(); ++ptr)
  865.         {
  866.             Vec2D delta = ptr->pred[0].pos - start;
  867.             if(!checkRay(start, delta, quad_index, ptr->quad_index))continue;
  868.             double dist = delta.len(), w = exp(-prm.dng_ang_att * (1 + ptr->turret * delta / dist));
  869.  
  870.             dist = max(0.0, dist - ptr->gun_len);
  871.             w *= sqr(sqr(1 - dist / shell_info[REGULAR].range));
  872.             double time = ptr->fire_time + shellFlyTime(dist, REGULAR);
  873.             danger[k] += w * exp(-time / prm.dng_lookahead) * fref[cur].danger * (ptr->premium ? prm.prem_danger + 1 : 1);
  874.             aggr[k] = max(aggr[k], (1 - dist / shell_info[REGULAR].range) * ptr->score_mul * aggr_mul);
  875.         }
  876.     }
  877.  
  878.     blur();  min_danger = prm.obst_danger;
  879.     for(size_t k = 0; k < width * height; k++)min_danger = min(min_danger, danger[k] -= aggr[k]);
  880.     //if(!cur)print();
  881.  
  882.     double best_target = 0;
  883.     gun_spd_p = max(1e-9, tank.turret_turn_speed() + prm.ang_spd_account * tank.angular_speed());
  884.     gun_spd_n = max(1e-9, tank.turret_turn_speed() - prm.ang_spd_account * tank.angular_speed());
  885.     for(vector<Target>::iterator ptr = target.begin(); ptr != target.end(); ++ptr)
  886.     {
  887.         Vec2D delta = ptr->pred[0].pos - fref[cur].pos;  GunMove res;
  888.         double angle = atan2(delta.y, delta.x), next = angle, da = M_PI / 18;
  889.         double best = checkTarget(*ptr, angle, next, res, 0), cur;
  890.         for(int i = 0; i < 4; i++)
  891.         {
  892.             best = checkTarget(*ptr, angle - da, next, res, best);
  893.             best = checkTarget(*ptr, angle + da, next, res, best);
  894.             best = checkTarget(*ptr, angle - 3 * da, next, res, best);
  895.             best = checkTarget(*ptr, angle + 3 * da, next, res, best);
  896.             angle = next;  da /= 2;
  897.         }
  898.         if(!fire_time)best = checkTarget(*ptr, fref[cur].gun_angle, next, res, best);
  899.         //if(best != 0 && res.fire_type)cout << "Firing, score: " << best << endl;
  900.         best *= ptr->score_mul;
  901.  
  902.         if(!(best > best_target))continue;  best_target = best;
  903.         gun_move = res.gun_move;  fire_type = res.fire_type;
  904.     }
  905. }
  906.  
  907. bool DangerField::checkRay(const Vec2D &start, const Vec2D &delta, size_t skip1, size_t skip2)
  908. {
  909.     Quad ray(start, delta, 7.5);
  910.     size_t list[] = {min(skip1, skip2), max(skip1, skip2), -1}, *skip = list;
  911.     for(size_t i = 0; i < quad.size(); i++)
  912.         if(i == *skip)skip++;
  913.         else if(quad[i].cross(ray))return false;
  914.     return true;
  915. }
  916.  
  917. double DangerField::checkRay(const ShellRef &shell, size_t skip1, size_t skip2)
  918. {
  919.     double res = numeric_limits<double>::infinity();
  920.     size_t list[] = {min(skip1, skip2), max(skip1, skip2), -1}, *skip = list;
  921.     for(size_t i = 0; i < quad.size(); i++)
  922.         if(i != *skip)
  923.         {
  924.             double t_min, t_max;
  925.             quad[i].crossRange(shell, shell.dir, t_min, t_max);
  926.             if(t_min < t_max && t_max > 0)res = min(res, t_min);
  927.         }
  928.         else skip++;
  929.     return max(0.0, res);
  930. }
  931.  
  932. void DangerField::blur()  // blur radius ~ 3.5 * h
  933. {
  934.     vector<double> buffer(danger.size() + 3 * width);
  935.  
  936.     size_t offs = 2 * width + 2, k = 0;
  937.     for(; k < 5 * width + 1; k++)buffer[k] = prm.obst_danger;
  938.     for(; k < danger.size() - width - 1; k++)
  939.     {
  940.         size_t pos = k - offs;
  941.         buffer[k] = (danger[pos] + danger[pos + 1] + danger[pos + 2] + danger[pos + 3] + danger[pos + 4]) / 5;
  942.     }
  943.     for(; k < danger.size() + 3 * width; k++)buffer[k] = prm.obst_danger;
  944.  
  945.     for(k = width + 1; k < danger.size() - width - 1; k++)
  946.     {
  947.         size_t pos = k;  double res = buffer[k];
  948.         pos += width;  res += buffer[pos];
  949.         pos += width;  res += buffer[pos];
  950.         pos += width;  res += buffer[pos];
  951.         pos += width;  res += buffer[pos];
  952.         buffer[k] = res / 5;
  953.     }
  954.  
  955.     static const double w1 = 0.8, w2 = 0.3;
  956.     static const double c0 = 1 / (29 + 8 * (w1 + w2)), c1 = w1 * c0, c2 = w2 * c0;
  957.     static const double cc = 25 * c0, ch = 2 * c0 + 4 * (c1 + c2);
  958.  
  959.     for(k = 0; k < 3 * width + 2; k++)
  960.     {
  961.         buffer[k] = cc * buffer[k] + ch * prm.obst_danger + c0 * (danger[k + 3 * width] + danger[k + 3]) +
  962.             c1 * (danger[k + 3 * width - 1] + danger[k + 3 * width + 1] + danger[k + width - 3] + danger[k + width + 3]) +
  963.             c2 * (danger[k + 3 * width - 2] + danger[k + 3 * width + 2] + danger[k + 2 * width - 3] + danger[k + 2 * width + 3]);
  964.     }
  965.     for(; k < danger.size() - 3 * width - 2; k++)
  966.     {
  967.         buffer[k] = cc * buffer[k] + c0 * (danger[k - 3 * width] + danger[k + 3 * width] + danger[k - 3] + danger[k + 3]) +
  968.             c1 * (danger[k - 3 * width - 1] + danger[k - 3 * width + 1] + danger[k + 3 * width - 1] + danger[k + 3 * width + 1] +
  969.                 danger[k - width - 3] + danger[k - width + 3] + danger[k + width - 3] + danger[k + width + 3]) +
  970.             c2 * (danger[k - 3 * width - 2] + danger[k - 3 * width + 2] + danger[k + 3 * width - 2] + danger[k + 3 * width + 2] +
  971.                 danger[k - 2 * width - 3] + danger[k - 2 * width + 3] + danger[k + 2 * width - 3] + danger[k + 2 * width + 3]);
  972.     }
  973.     for(; k < danger.size(); k++)
  974.     {
  975.         buffer[k] = cc * buffer[k] + ch * prm.obst_danger + c0 * (danger[k - 3 * width] + danger[k - 3]) +
  976.             c1 * (danger[k - 3 * width - 1] + danger[k - 3 * width + 1] + danger[k - width - 3] + danger[k - width + 3]) +
  977.             c2 * (danger[k - 3 * width - 2] + danger[k - 3 * width + 2] + danger[k - 2 * width - 3] + danger[k - 2 * width + 3]);
  978.     }
  979.  
  980.     buffer.resize(danger.size());  danger.swap(buffer);
  981. }
  982.  
  983. double DangerField::sampleDanger(const Vec2D &pos)
  984. {
  985.     Vec2D index = (pos - offset) / h;
  986.     size_t i = size_t(floor(index.x)), j = size_t(floor(index.y));
  987.     if(i >= width - 1 || j >= height - 1)return prm.obst_danger;
  988.  
  989.     index -= Vec2D(i, j);  size_t k = i + j * width;
  990.     double up = danger[k] + (danger[k + 1] - danger[k]) * index.x;  k += width;
  991.     double dn = danger[k] + (danger[k + 1] - danger[k]) * index.x;
  992.     return up + (dn - up) * index.y;
  993. }
  994.  
  995. double DangerField::hitDanger(const State &state, size_t index, int step)
  996. {
  997.     size_t pindex = step * sref.size() + index;
  998.     if(!checkRay(shell_pos[pindex], shell_pos[pindex] - shell_pos[index], quad_index))return 0;
  999.  
  1000.     double dot = sref[index].dir * state.dir, cross = sref[index].dir % state.dir;
  1001.     double w = dot > 0 ? -state.half_w : state.half_w, h = cross > 0 ? -state.half_h : state.half_h;
  1002.     double offs = (state.pos + w * state.dir + h * ~state.dir - shell_pos[pindex]) % sref[index].dir;
  1003.     if(dot * cross > 0)offs = -offs;
  1004.  
  1005.     static const double back = 1 / 1.0, side = 1 / 1.5, front = 1 / 1.75;
  1006.  
  1007.     double mul = prm.hit_danger * prm.obst_danger * sref[index].score;
  1008.     mul *= (shell_pos[pindex] - shell_pos[pindex - sref.size()]).len();
  1009.     if(offs < -sref[index].half_h)return side * mul * sqr(cross);
  1010.     if(offs > sref[index].half_h)return (dot > 0 ? back : front) * mul * sqr(dot);
  1011.     return (dot > 0 ? back : side) * mul;
  1012. }
  1013.  
  1014. double DangerField::samplePhys(State state, size_t index, const size_t *max_act,
  1015.     double mul, double sum, vector<bool> flag, double best, int step)
  1016. {
  1017.     for(step++;; step++)
  1018.     {
  1019.         state.advance(act[index], size);  double dng = sampleDanger(state.pos);
  1020.         //if(!index && !(state.spd.sqr() > sqr(0.05 * h)) || !(mul > 1e-3))return min(best, sum + dng * mul);
  1021.         if(!index && step > 64 || !(mul > 1e-3))return min(best, sum + dng * mul);  // TODO: shell stop
  1022.         sum += dng * mul * (1 - dmul);
  1023.  
  1024.         if(step >= fire_time && flag[0] &&
  1025.             abs(rem(state.angle - tg_angle + M_PI, 2 * M_PI) - M_PI) < step * gun_spd)
  1026.         {
  1027.             sum -= prm.rot_bonus * mul;  flag[0] = false;
  1028.         }
  1029.  
  1030.         size_t fpos = 1;
  1031.         for(size_t j = 0; j < bref.size(); j++)
  1032.             if(flag[fpos + j] && state.checkPoint(bref[j].pos))
  1033.             {
  1034.                 sum -= bonus_score[bref[j].type] * mul;  flag[fpos + j] = false;
  1035.             }
  1036.  
  1037.         size_t offs = step * sref.size();  fpos += bref.size();
  1038.         while(shell_pos.size() < offs + sref.size())
  1039.             for(size_t j = 0; j < sref.size(); j++)
  1040.             {
  1041.                 sref[j].advance();  shell_pos.push_back(sref[j].pos);
  1042.             }
  1043.         for(size_t j = 0; j < sref.size(); j++)
  1044.             if(flag[fpos + j] && state.cross(sref[j].move(shell_pos[offs + j])))
  1045.             {
  1046.                 sum += hitDanger(state, j, step) * mul;  flag[fpos + j] = false;
  1047.             }
  1048.  
  1049.         mul *= dmul;
  1050.         double min_total = min_danger - (flag[0] ? prm.rot_bonus : 0) - max_bonus;
  1051.         if(!(sum + min_total * mul < best))return best;
  1052.  
  1053.         if(index && !(step % 32))for(size_t i = 0; i < *max_act; i++)if(i != index)
  1054.             best = samplePhys(state, i, max_act + 1, mul, sum, flag, best, step);
  1055.     }
  1056. }
  1057.  
  1058. size_t DangerField::samplePhys(const Tank &tank, const double move[][2], const size_t *max_move)
  1059. {
  1060.     size_t move_count = 1;
  1061.     for(const size_t *ptr = max_move; *ptr > 1; ptr++)move_count = max(move_count, *ptr);
  1062.  
  1063.     act.resize(move_count);
  1064.     for(size_t i = 0; i < move_count; i++)act[i] = Action(tank, move[i][0], move[i][1]);
  1065.  
  1066.     BonusRef::calcScore(tank, bonus_score);
  1067.     tg_angle = tank.angle() + gun_move;
  1068.     gun_spd = tank.turret_turn_speed();
  1069.  
  1070.     State state(tank);
  1071.     double dng = sampleDanger(state.pos);
  1072.     double mul = dmul, sum = dng * (1 - mul);
  1073.     vector<bool> flag(bref.size() + sref.size() + 1, true);
  1074.     flag[0] = fire_time;
  1075.  
  1076.     double best = numeric_limits<double>::infinity();
  1077.     size_t dir = 0, prev = fref[cur].prev_dir;
  1078.     if(prev < move_count)
  1079.     {
  1080.         best = samplePhys(state, prev, max_move + 1, mul, sum, flag, best);
  1081.         dir = prev;
  1082.     }
  1083.     for(size_t i = 0; *max_move > 1; max_move++)
  1084.         for(; i < *max_move; i++)if(i != prev)
  1085.         {
  1086.             double res = samplePhys(state, i, max_move + 1, mul, sum, flag, best);
  1087.             if(!(res < best))continue;  best = res;  dir = i;
  1088.         }
  1089.     //cout << "Best dir: " << dir << ", danger: " << best << endl;
  1090.     return fref[cur].prev_dir = dir;
  1091. }
  1092.  
  1093.  
  1094. double DangerField::checkTarget(const Target &tank, double angle, double &best_angle, GunMove &res, double best)
  1095. {
  1096.     double a = rem(angle - fref[cur].gun_angle - fire_time * fref[cur].ang_spd, 2 * M_PI);
  1097.     double left_time = (2 * M_PI - a) / gun_spd_n, right_time = a / gun_spd_p;  int start;
  1098.     if(left_time < right_time)
  1099.     {
  1100.         start = (int)ceil(left_time);  a -= 2 * M_PI;
  1101.     }
  1102.     else start = (int)ceil(right_time);
  1103.     start = max(0, start - fire_time);
  1104.  
  1105.     Vec2D dir = sincos(angle);
  1106.     ShellRef shell(fref[cur].pos, dir, fref[cur].gun_len, REGULAR);
  1107.     double dist = checkRay(shell, quad_index, tank.quad_index);
  1108.     int total = (int)min(1e6, ceil(shellFlyTime(dist, REGULAR)));
  1109.     double sc = tank.calcScore(shell, start, total);
  1110.     FireType fire = REGULAR_FIRE;
  1111.     if(fref[cur].premium)
  1112.     {
  1113.         shell = ShellRef(fref[cur].pos, dir, fref[cur].gun_len, PREMIUM);
  1114.         total = (int)min(1e6, ceil(shellFlyTime(dist, PREMIUM)));
  1115.         double sc_p = (prm.tg_prem_bonus + 1) * tank.calcScore(shell, start, total) - prm.tg_prem_offs;
  1116.         if(sc_p > sc)
  1117.         {
  1118.             sc = sc_p;  fire = PREMIUM_FIRE;
  1119.         }
  1120.     }
  1121.     if(!(sc > best))return best;
  1122.  
  1123.     if(sc < prm.tg_fire_thr && (cur_tick % 64 || cur_tick / 64 % fref.size() != cur))fire = NONE;
  1124.  
  1125.     res.fire_type = (!fire_time && abs(a) < 1e-3 ? fire : NONE);
  1126.     best_angle = angle;  res.gun_move = a - fref[cur].ang_spd;  return sc;
  1127. }
  1128.  
  1129.  
  1130. void Target::generate(const Tank &tank)
  1131. {
  1132.     delta_min = -tank.engine_rear_power_factor();  delta_max = 1;
  1133.  
  1134.     double damp = tank_info[tank.type()].damp;
  1135.     double rot_damp = tank_info[tank.type()].rot_damp;
  1136.     double force = 0.5 + tank.crew_health() / (2.0 * tank.crew_max_health());
  1137.     force *= tank_info[tank.type()].force;
  1138.  
  1139.     pred.resize(max_pred);  pred[0].pos = Vec2D(tank.x(), tank.y());
  1140.     pred[0].delta = Vec2D(0, 0);  pred[0].dir = sincos(tank.angle());
  1141.     pred[0].min = delta_min;  pred[0].max = delta_max;
  1142.  
  1143.     Vec2D spd(tank.speed_x(), tank.speed_y()), spd_delta(0, 0);
  1144.     double angle(tank.angle()), ang_spd(tank.angular_speed());
  1145.     for(int i = 1; i < max_pred; i++)
  1146.     {
  1147.         spd_delta += force * pred[i - 1].dir - damp * spd_delta;
  1148.         spd -= damp * spd;  ang_spd -= rot_damp * ang_spd;
  1149.  
  1150.         pred[i].pos = pred[i - 1].pos + spd;
  1151.         pred[i].delta = pred[i - 1].delta + spd_delta;
  1152.         pred[i].dir = sincos(angle += ang_spd);
  1153.  
  1154.         double border = half_w / pred[i].delta.len();
  1155.         Vec2D inv(1 / pred[i].delta.x, 1 / pred[i].delta.y);
  1156.         Vec2D delta = DangerField::size / 2, center = delta - pred[i].pos;
  1157.         if(inv.x < 0)delta.x = -delta.x;  if(inv.y < 0)delta.y = -delta.y;
  1158.         double cur_min = max(pred[i - 1].min - border, max((center.x - delta.x) * inv.x, (center.y - delta.y) * inv.y));
  1159.         double cur_max = min(pred[i - 1].max + border, min((center.x + delta.x) * inv.x, (center.y + delta.y) * inv.y));
  1160.         for(size_t j = 0; j < DangerField::block_count; j++)
  1161.             if(j != quad_index)
  1162.             {
  1163.                 double t_min, t_max;
  1164.                 DangerField::quad[j].crossLine(pred[i].pos, pred[i].delta, t_min, t_max);
  1165.                 if(t_min < cur_min && t_max > cur_min)cur_min = t_max;
  1166.                 if(t_min < cur_max && t_max > cur_max)cur_max = t_min;
  1167.             }
  1168.         cur_min += border;  cur_max -= border;
  1169.         if(cur_min > cur_max)cur_min = cur_max = (cur_min + cur_max) / 2;
  1170.         pred[i].min = cur_min;  pred[i].max = cur_max;
  1171.     }
  1172. }
  1173.  
  1174. void Target::calcRange(ShellRef shell, int step, int total, ScoreRange &range) const
  1175. {
  1176.     double score = exp(-step / prm.tg_lookahead);
  1177.     int end = step + total;  if(end > max_pred)end = max_pred;
  1178.     for(; step < end; step++, score *= dmul)
  1179.     {
  1180.         double t_min, t_max;
  1181.         shell.crossRange(Quad(pred[step].pos, pred[step].dir, half_w, half_h), pred[step].delta, t_min, t_max);
  1182.         t_min = max(pred[step].min, t_min);  t_max = min(pred[step].max, t_max);
  1183.         if(t_min < t_max)
  1184.         {
  1185.             double score1 = score * sqr(shell.dir * pred[step].dir);
  1186.             double score2 = score * sqr(shell.dir % pred[step].dir);
  1187.  
  1188.             Vec2D dr = shell.pos - pred[step].pos;
  1189.             if(dr % pred[step].delta < 0)swap(score1, score2);
  1190.             Vec2D diag1 = half_w * pred[step].dir + half_h * ~pred[step].dir;
  1191.             Vec2D diag2 = half_w * pred[step].dir - half_h * ~pred[step].dir;
  1192.             double div1 = (dr % diag1) / (pred[step].delta % diag1);
  1193.             double div2 = (dr % diag2) / (pred[step].delta % diag2);
  1194.             if(div1 > div2)
  1195.             {
  1196.                 swap(div1, div2);  swap(score1, score2);
  1197.             }
  1198.  
  1199.             int index = 1;
  1200.             ScoreElem elem[4] = {ScoreElem(t_min == pred[step].min ? delta_min : t_min, score1)};
  1201.             if(div1 > t_min)
  1202.             {
  1203.                 if(div1 < t_max)
  1204.                 {
  1205.                     elem[index++] = ScoreElem(div1, score2);
  1206.                     if(div2 < t_max)elem[index++] = ScoreElem(div2, score1);
  1207.                 }
  1208.             }
  1209.             else if(div2 > t_min)
  1210.             {
  1211.                 elem[0].val = score2;
  1212.                 if(div2 < t_max)elem[index++] = ScoreElem(div2, score1);
  1213.             }
  1214.             elem[index++] = ScoreElem(t_max == pred[step].max ? delta_max : t_max, 0);
  1215.             range.merge(elem, index);
  1216.         }
  1217.         shell.advance();
  1218.     }
  1219. }
  1220.  
  1221.  
  1222. inline void printValues(double up, double dn, int flag)
  1223. {
  1224.     static const char gradient[] =
  1225.         "000 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 015";
  1226.  
  1227.     cout << "\x1B[48;5;";
  1228.     if(flag & 1)cout << 10;
  1229.     else cout.write(gradient + 4 * min(max(0, int(up * 26)), 25), 3);  cout << ";38;5;";
  1230.     if(flag & 2)cout << 10;
  1231.     else cout.write(gradient + 4 * min(max(0, int(dn * 26)), 25), 3);  cout << "m▄";
  1232. }
  1233.  
  1234. void DangerField::print()
  1235. {
  1236.     static const double offs = 0, scale = 0.5;
  1237.  
  1238.     Vec2D index = (fref[cur].pos - offset) / h;
  1239.     size_t k0 = size_t(floor(index.x + 0.5)) + size_t(floor(index.y + 0.5)) * width;
  1240.  
  1241.     cout << "\x1B[" << height << 'A';
  1242.     for(size_t j = 0, k = 0; j < height; j += 2, k += width)
  1243.     {
  1244.         for(size_t i = 0; i < width; i++, k++)
  1245.             printValues((danger[k] + offs) * scale, (danger[k + width] + offs) * scale,
  1246.                 k == k0 ? 1 : k + width == k0 ? 2 : 0);
  1247.         cout << "\x1B[0m" << endl;
  1248.     }
  1249. }
  1250.  
  1251.  
  1252. clock_t global_time;
  1253.  
  1254. void MyStrategy::Move(Tank self, World world, model::Move& move)
  1255. {
  1256.     DangerField field(world, self);
  1257.     if(field.cur == size_t(-1))return;
  1258.  
  1259.     move.set_fire_type(field.fire_type);
  1260.     move.set_turret_turn(field.gun_move);
  1261.  
  1262.  
  1263.     static const double moves[][2] =
  1264.     {
  1265.         {0, 0}, {1, -1}, {-1, 1}, {1, 1}, {-1, -1},
  1266.         {1, 0.9}, {0.9, 1}, {-1, -0.9}, {-0.9, -1},
  1267.         {1, 0.8}, {0.8, 1}, {-1, -0.8}, {-0.8, -1},
  1268.         {1, 0.7}, {0.7, 1}, {-1, -0.7}, {-0.7, -1},
  1269.         {1, 0.6}, {0.6, 1}, {-1, -0.6}, {-0.6, -1},
  1270.         //{1, 0.5}, {0.5, 1}, {-1, -0.5}, {-0.5, -1},
  1271.         {1, 0.4}, {0.4, 1}, {-1, -0.4}, {-0.4, -1},
  1272.         //{1, 0.3}, {0.3, 1}, {-1, -0.3}, {-0.3, -1},
  1273.         {1, 0.2}, {0.2, 1}, {-1, -0.2}, {-0.2, -1},
  1274.         //{1, 0.1}, {0.1, 1}, {-1, -0.1}, {-0.1, -1},
  1275.         {1, 0.0}, {0.0, 1}, {-1, -0.0}, {-0.0, -1},
  1276.         //{1, -0.1}, {-0.1, 1}, {-1, 0.1}, {0.1, -1},
  1277.         {1, -0.2}, {-0.2, 1}, {-1, 0.2}, {0.2, -1},
  1278.         //{1, -0.3}, {-0.3, 1}, {-1, 0.3}, {0.3, -1},
  1279.         {1, -0.4}, {-0.4, 1}, {-1, 0.4}, {0.4, -1},
  1280.         //{1, -0.5}, {-0.5, 1}, {-1, 0.5}, {0.5, -1},
  1281.         {1, -0.6}, {-0.6, 1}, {-1, 0.6}, {0.6, -1},
  1282.         //{1, -0.7}, {-0.7, 1}, {-1, 0.7}, {0.7, -1},
  1283.         {1, -0.8}, {-0.8, 1}, {-1, 0.8}, {0.8, -1},
  1284.         //{1, -0.9}, {-0.9, 1}, {-1, 0.9}, {0.9, -1},
  1285.     };
  1286.  
  1287.     static const size_t max_move[] = {sizeof(moves) / sizeof(moves[0]), 1};
  1288.  
  1289.     size_t dir = field.samplePhys(self, moves, max_move);
  1290.     move.set_left_track_power(moves[dir][0]);
  1291.     move.set_right_track_power(moves[dir][1]);
  1292.  
  1293.  
  1294.     /*if(world.tick() % 100 == 99)
  1295.     {
  1296.         clock_t old = global_time;  global_time = clock();
  1297.         cout << "Time per tick: " << (global_time - old) * (10.0 / CLOCKS_PER_SEC) << "ms" << endl;
  1298.     }*/
  1299. }
  1300.  
  1301. TankType MyStrategy::SelectTank(int tank_index, int team_size)
  1302. {
  1303.     global_time = clock();
  1304.  
  1305.     return MEDIUM;
  1306. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top