API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jul 22nd, 2017
50
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 13.70 KB | None | 0 0
raw download clone embed print report
  1. #include <cstdio>
  2. #include <complex>
  3. #include <cstring>
  4. #include <string>
  5. #include <cmath>
  6. #include <cstdlib>
  7. #include <algorithm>
  8. #include <vector>
  9. #include <queue>
  10. #include <deque>
  11. #include <set>
  12. #include <map>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <numeric>
  16. #include <climits>
  17.  
  18. using namespace std;
  19.  
  20. int nextInt() {
  21.     int x;
  22.     scanf("%d", &x);
  23.     return x;
  24. }
  25.  
  26. double nextDouble() {
  27.     double x;
  28.     scanf("%lf", &x);
  29.     return x;
  30. }
  31.  
  32. long long nextLong() {
  33.     long long x;
  34.     scanf("%I64d", &x);
  35.     return x;
  36. }
  37.  
  38. const int BUFSIZE = 10000010;
  39. char buf[BUFSIZE + 1];
  40. string nextString() {
  41.     scanf("%s", buf);
  42.     return buf;
  43. }
  44.  
  45. string nextLine() {
  46.     gets(buf);
  47.     return buf;
  48. }
  49.  
  50. const bool DEBUG_ON = false;
  51. template <class T>
  52. void debug(vector<T> &a, string name) {
  53.     cerr << name << ": ";
  54.     for (int i = 0; i < a.size(); ++i) {
  55.         cerr << a[i] << " ";
  56.     }
  57.     cerr << endl;
  58. }
  59.  
  60. struct Point {
  61.     double x, y;
  62.     Point () {}
  63.     Point (double x, double y) : x(x), y(y) {}
  64.     Point operator + (const Point &op) const { return Point(x + op.x, y + op.y); }
  65.     Point operator - (const Point &op) const { return Point(x - op.x, y - op.y); }
  66.     Point operator * (const double &op) const { return Point(x * op, y * op); }
  67.     double operator * (const Point &op) const { return x * op.x + y * op.y; }
  68.     double operator % (const Point &op) const { return x * op.y - y * op.x; }
  69.     string toString() const {
  70.         stringstream out;
  71.         out << "(" << x << ", " << y << ")";
  72.         return out.str();
  73.     }
  74.     double length() {
  75.         return sqrt(x * x + y * y);
  76.     }
  77. };
  78.  
  79. Point nextPoint() {
  80.     double x = nextDouble();
  81.     double y = nextDouble();
  82.     return Point(x, y);
  83. }
  84.  
  85. struct Moto {
  86.     Point startPoint;
  87.     Point dir;
  88.     int id;
  89.     Moto () {}
  90.     Moto (Point startPoint, Point dir, int id) : startPoint(startPoint), dir(dir), id(id) {}
  91. };
  92.  
  93. Moto nextMoto(int id) {
  94.     Point start = nextPoint();
  95.     Point dir = nextPoint();
  96.     return Moto(start, dir, id);
  97. }
  98.  
  99. const double inf = 1e20;
  100. const double eps = 1e-9;
  101.  
  102. int cmp(double x, double y) {
  103.     double tol = eps * max(1.0, max(fabs(x), fabs(y)));
  104.     return x - y < -tol ? -1 : x - y > tol ? 1 : 0;
  105. }
  106.  
  107. bool isGt(double x, double y) {
  108.     return cmp(x, y) > 0;
  109. }
  110.  
  111. bool isEqual(double x, double y) {
  112.     return cmp(x, y) == 0;
  113. }
  114.  
  115. struct Event {
  116.     int id;
  117.     Point point;
  118.     int kind;
  119.     int winId;
  120.     Event () {}
  121.     Event (int id, Point point, int kind, int winId = -1) : id(id), point(point), kind(kind), winId(winId) {}
  122.     bool operator < (const Event &op) const {
  123.         if (!isEqual(point.x, op.point.x)) {
  124.             return point.x < op.point.x;
  125.         }
  126.         if (kind != op.kind) {
  127.             return kind < op.kind;
  128.         }
  129.         if (!isEqual(point.y, op.point.y)) {
  130.             return point.y < op.point.y;
  131.         }
  132.         if (id != op.id) {
  133.             return id < op.id;
  134.         }
  135.         return winId < op.winId;
  136.     }
  137. };
  138.  
  139. double getIntPar(Point s1, Point e1, Point s2, Point e2) {
  140.     double d = (e1 - s1) % (e2 - s2);
  141.     if (fabs(d) <= eps) {
  142.         return inf;
  143.     }
  144.     return -((s1 - s2) % (e2 - s2)) / d;
  145. }
  146.  
  147. Point getEndPoint(Moto moto, double W, double H) {
  148.     double par = inf;
  149.     vector<pair<Point, Point> > lines;
  150.     for (int m1 = 0; m1 < 4; ++m1) {
  151.         for (int m2 = m1 + 1; m2 < 4; ++m2) {
  152.             int x = m1 ^ m2;
  153.             if ((x & (x - 1)) == 0) {
  154.                 Point p1(m1 & 1 ? -W : W, m1 & 2 ? -H : H);
  155.                 Point p2(m2 & 1 ? -W : W, m2 & 2 ? -H : H);
  156.                 lines.push_back(make_pair(p1, p2));
  157.             }
  158.         }
  159.     }
  160.     Point s = moto.startPoint;
  161.     Point e = moto.startPoint + moto.dir;
  162.     for (int i = 0; i < lines.size(); ++i) {
  163.         double p = getIntPar(s, e, lines[i].first, lines[i].second);
  164.         if (p > eps) {
  165.             par = min(par, p);
  166.         }
  167.     }
  168.     return s + (e - s) * par;
  169. }
  170.  
  171. struct SweepMoto {
  172.     static vector<Moto> *motos;
  173.     static Point sweepPoint;
  174.     int ind;
  175.     SweepMoto (int ind) : ind(ind) {}
  176.     bool operator < (const SweepMoto &op) const {
  177.         double curY = getY();
  178.         double opY = op.getY();
  179.         if (curY != opY) {
  180. //      if (fabs(curY - opY) > eps) {
  181.             return curY < opY;
  182.         }
  183.         return ind < op.ind;
  184.     }
  185.     double getY() const {
  186.         double tol = eps * max(1.0, fabs(sweepPoint.x));
  187.         double x = sweepPoint.x - tol;
  188.         double y = (*motos)[ind].startPoint.y + (*motos)[ind].dir.y * (x - (*motos)[ind].startPoint.x) / (*motos)[ind].dir.x;
  189.         return y;
  190.     }
  191. };
  192.  
  193. vector<Moto> * SweepMoto::motos = 0;
  194. Point SweepMoto::sweepPoint;
  195.  
  196. bool getMotosBreak(Moto &m1, Moto &m2, Point &crossPoint) {
  197.     Point s1 = m1.startPoint;
  198.     Point e1 = s1 + m1.dir;
  199.     Point s2 = m2.startPoint;
  200.     Point e2 = s2 + m2.dir;
  201.     double p1 = getIntPar(s1, e1, s2, e2);
  202.     double p2 = getIntPar(s2, e2, s1, e1);
  203.     if (fabs(p1) <= eps || fabs(p2) <= eps) {
  204.         cerr << "collision found\n" << endl;
  205.         throw 0;
  206.     }
  207.     if (p1 > eps && p2 > eps && p1 < inf) {
  208.         crossPoint = s1 + (e1 - s1) * p1;
  209.         return true;
  210.     }
  211.     return false;
  212. }
  213.  
  214. double getTime(Moto &moto, Point &dst) {
  215.     return (dst - moto.startPoint).length() / moto.dir.length();
  216. }
  217.  
  218. void addMotosBreakEvent(set<Event> &events, Moto &m1, Moto &m2) {
  219.     Point crossPoint;
  220.     if (getMotosBreak(m1, m2, crossPoint)) {
  221.         double t1 = getTime(m1, crossPoint);
  222.         double t2 = getTime(m2, crossPoint);
  223.         if (DEBUG_ON) {
  224.             cerr << "times = " << t1 << " " << t2 << endl;
  225.         }
  226.         int id = t1 > t2 ? m1.id : m2.id;
  227.         events.insert(Event(id, crossPoint, -1, m1.id ^ m2.id ^ id));
  228.     }
  229. }
  230.  
  231. void addMoto(set<SweepMoto> &sweepLine, set<Event> &events, int motoId) {
  232.     set<SweepMoto>::iterator it = sweepLine.insert(SweepMoto(motoId)).first;
  233.     vector<Moto> &motos = *SweepMoto::motos;
  234.     if (it != sweepLine.begin()) {
  235.         set<SweepMoto>::iterator prev = it;
  236.         --prev;
  237.         addMotosBreakEvent(events, motos[prev->ind], motos[it->ind]);
  238.     }
  239.     {
  240.         set<SweepMoto>::iterator next = it;
  241.         if (++next != sweepLine.end()) {
  242.             addMotosBreakEvent(events, motos[next->ind], motos[it->ind]);
  243.         }
  244.     }
  245. }
  246.  
  247. double removeMoto(set<SweepMoto> &sweepLine, set<Event> &events, int motoId, int winId) {
  248.     set<SweepMoto>::iterator it = sweepLine.find(SweepMoto(motoId));
  249.     set<SweepMoto>::iterator winIt = winId == -1 ? sweepLine.end() : sweepLine.find(SweepMoto(winId));
  250.     if (DEBUG_ON) {
  251.         cerr << "winId = " << winId << endl;
  252.     }
  253.     if (it == sweepLine.end() || winId != -1 && winIt == sweepLine.end()) {
  254.         if (DEBUG_ON) {
  255.             cerr << "sweepPoint = " << SweepMoto::sweepPoint.toString() << endl;
  256.             cerr << motoId << " erasing failed" << endl;
  257.         }
  258.         return 0;
  259.     }
  260.     vector<Moto> &motos = *SweepMoto::motos;
  261.     if (it != sweepLine.begin()) {
  262.         set<SweepMoto>::iterator prev = it;
  263.         --prev;
  264.         set<SweepMoto>::iterator next = it;
  265.         if (++next != sweepLine.end()) {
  266.             addMotosBreakEvent(events, motos[prev->ind], motos[next->ind]);
  267.         }
  268.     }
  269.     double res = getTime(motos[it->ind], SweepMoto::sweepPoint) * motos[it->ind].dir.length();
  270.     sweepLine.erase(it);
  271.     return res;
  272. }
  273.  
  274. double solve(double W, double H, vector<Moto> motos) {
  275.     set<Event> events;
  276.     for (int i = 0; i < motos.size(); ++i) {
  277.         events.insert(Event(i, motos[i].startPoint, +1));
  278.         Point endPoint = getEndPoint(motos[i], W, H);
  279.         if (DEBUG_ON) {
  280.             cerr << i << " " << endPoint.toString() << endl;
  281.         }
  282.         events.insert(Event(i, endPoint, -1));
  283.     }
  284.     SweepMoto::motos = &motos;
  285.     set<SweepMoto> sweepLine;
  286.     double res = 0;
  287.     while (events.empty() == false) {
  288.         if (DEBUG_ON) {
  289.             cerr << "events size = " << events.size() << " ---------------------" << endl;
  290.             for (set<Event>::iterator it = events.begin(); it != events.end(); ++it) {
  291.                 cerr << it->id << " " << it->point.toString() << " " << it->kind << endl;
  292.             }
  293.             cerr << "sweep size = " << sweepLine.size() << endl;
  294.             for (set<SweepMoto>::iterator it = sweepLine.begin(); it != sweepLine.end(); ++it) {
  295.                 cerr << it->ind << endl;
  296.             }
  297.         }
  298.         Event curEvent = *events.begin();
  299.         events.erase(events.begin());
  300.         SweepMoto::sweepPoint = curEvent.point;
  301.         if (curEvent.kind == +1) {
  302.             addMoto(sweepLine, events, curEvent.id);
  303.         } else {
  304.             double len = removeMoto(sweepLine, events, curEvent.id, curEvent.winId);
  305.             if (DEBUG_ON) {
  306.                 cerr << curEvent.id << ": " << "len = " << len << endl;
  307.             }
  308.             res += len;
  309.         }
  310.     }
  311.     return res;
  312. }
  313.  
  314. double randomDouble() {
  315.     return ((rand() << 15) + rand()) % 1000000 / 1e6;
  316.     //return rand() / double(1 << 15);
  317. }
  318.  
  319. Point randomPoint(double W, double H) {
  320.     int w = W;
  321.     int h = H;
  322.     double x = rand() % w;
  323.     double y = rand() % h;
  324.     //double x = randomDouble() * 2 * W - W;
  325.     //double y = randomDouble() * 2 * H - H;
  326.     return Point(x, y);
  327. }
  328.  
  329. Moto randomMoto(int id, double W, double H) {
  330.     Point start = Point(randomDouble() * 2 * (W - 1) - (W - 1), randomDouble() * 2 * (H - 1) - (H - 1));
  331.     Point dir = Point(randomDouble() * 10 + 0.00001, randomDouble() * 20 - 10);
  332.     return Moto(start, dir, id);
  333. }
  334.  
  335. struct Segment {
  336.     Point s, e;
  337.     Segment (Point s, Point e) : s(s), e(e) {}
  338. };
  339.  
  340. double getDeathTime(Moto m, vector<Moto> &motos, vector<Segment> &walls) {
  341.     double par = inf;
  342.     Point s = m.startPoint;
  343.     Point e = s + m.dir;
  344.     for (int i = 0; i < motos.size(); ++i) {
  345.         if (motos[i].id != m.id) {
  346.             Point ms = motos[i].startPoint;
  347.             Point me = ms + motos[i].dir;
  348.             double p = getIntPar(s, e, ms, me);
  349.             double mp = getIntPar(ms, me, s, e);
  350.             if (mp > eps && p > eps && p > mp) {
  351.                 par = min(par, p);
  352.             }
  353.         }
  354.     }
  355.     for (int i = 0; i < walls.size(); ++i) {
  356.         Point ms = walls[i].s;
  357.         Point me = walls[i].e;
  358.         double p = getIntPar(s, e, ms, me);
  359.         double mp = getIntPar(ms, me, s, e);
  360.         if (eps < mp && mp < 1 - eps && p > eps) {
  361.             par = min(par, p);
  362.         }
  363.     }
  364.     return par;
  365. }
  366.  
  367. double solveSlow(double W, double H, vector<Moto> motos) {
  368.     vector<Segment> walls;
  369.     Point p00(-W, -H);
  370.     Point p01(-W, H);
  371.     Point p10(W, -H);
  372.     Point p11(W, H);
  373.     Point dx(1, 0), dy(0, 1);
  374.     walls.push_back(Segment(p00 - dy, p01 + dy));
  375.     walls.push_back(Segment(p00 - dx, p10 + dx));
  376.     walls.push_back(Segment(p11 + dx, p01 - dx));
  377.     walls.push_back(Segment(p11 + dy, p10 - dy));
  378.     double res = 0;
  379.     while (motos.size() > 0) {
  380.         double minTime = inf;
  381.         double minSpeed = inf;
  382.         for (int i = 0; i < motos.size(); ++i) {
  383.             double curTime = getDeathTime(motos[i], motos, walls);
  384.             double curSpeed = motos[i].dir.length();
  385.             if (DEBUG_ON) {
  386. //              cerr << "m: curTime = " << curTime << endl;
  387. //              cerr << "m: curSpeed = " << curSpeed << endl;
  388.             }
  389.             if (isGt(minTime, curTime) || isEqual(minTime, curTime) && isGt(minSpeed, curSpeed)) {
  390.                 minTime = curTime;
  391.                 minSpeed = curSpeed;
  392.             }
  393.         }
  394.         for (int i = 0; i < motos.size(); ++i) {
  395.             double curTime = getDeathTime(motos[i], motos, walls);
  396.             double curSpeed = motos[i].dir.length();
  397.             if (DEBUG_ON) {
  398. //              cerr << "w: curTime = " << curTime << endl;
  399. //              cerr << "w: curSpeed = " << curSpeed << endl;
  400.             }
  401.             if (minTime == curTime && minSpeed == curSpeed) {
  402.                 Point startPoint = motos[i].startPoint;
  403.                 Point endPoint = motos[i].startPoint + motos[i].dir * minTime;
  404.                 double len = (endPoint - startPoint).length();
  405.                 res += len;
  406.                 walls.push_back(Segment(startPoint, endPoint));
  407. //              cerr << motos[i].id << " id deleted" << endl;
  408.                 if (DEBUG_ON) {
  409.                     cerr << motos[i].id << ": " << "len = " << len << endl;
  410.                     cerr << "minTime = " << minTime << endl;
  411.                     cerr << "minSpeed = " << minSpeed << endl;
  412.                 }
  413.                 motos.erase(motos.begin() + i);
  414.                 break;
  415.             }
  416.         }
  417.     }
  418.     return res;
  419. }
  420.  
  421. int main() {
  422.     {
  423.         for (int seed = 0; seed < 100000; ++seed) {
  424.             srand(seed);
  425.             if (seed % 100 == 0) {
  426.                 cerr << "seed = " << seed << endl;
  427.             }
  428.             //cout << seed << ": " << res << endl;
  429.             int n = 100;//((rand() << 15) + rand()) % 20 + 1;
  430.             double W = 10000;
  431.             double H = 10000;
  432.             vector<Moto> motos(n);
  433.             for (int i = 0; i < n; ++i) {
  434.                 while (true) {
  435.                     motos[i] = randomMoto(i, W, H);
  436.                     bool ok = true;
  437.                     /*
  438.                     for (int j = 0; j < i; ++j) {
  439.                         Point s1 = motos[i].startPoint;
  440.                         Point e1 = s1 + motos[i].dir;
  441.                         Point s2 = motos[j].startPoint;
  442.                         Point e2 = s2 + motos[j].dir;
  443.                         if (fabs((s2 - s1) % motos[i].dir) <= eps
  444.                                 || fabs((s1 - s2) % motos[j].dir) <= eps) {
  445.                             ok = false;
  446.                             break;
  447.                         }
  448.                         double p1 = getIntPar(s1, e1, s2, e2);
  449.                         double p2 = getIntPar(s1, e1, s2, e2);
  450.                         if (eps < p1 && p1 < inf && eps < p2 && p2 < inf && fabs(p1 - p2) <= eps) {
  451.                             ok = false;
  452.                             break;
  453.                         }
  454.                     }
  455.                     */
  456.                     if (ok) {
  457.                         break;
  458.                     }
  459.                 }
  460.             }
  461.             if (DEBUG_ON) {
  462.                 cout << n << " " << W << " " << H << endl;
  463.                 for (int i = 0; i < motos.size(); ++i) {
  464.                     cout << motos[i].startPoint.x << " " << motos[i].startPoint.y << " " << motos[i].dir.x << " " << motos[i].dir.y << endl;
  465.                 }
  466.             }
  467.             double res = solve(W, H, motos);
  468.             double resSlow = solveSlow(W, H, motos);
  469.             cout << ".";
  470. //          cerr << "time = " << clock() << endl;
  471.             if (!(res >= 0)) {
  472.                 cerr << "res = " << res << endl;
  473.                 cerr << "seed = " << seed << endl;
  474.                 break;
  475.             }
  476.             if (fabs(res - resSlow) > 1e-6) {
  477.                 cerr << "seed = " << seed << endl;
  478.                 cerr.precision(10);
  479.                 cerr << res << endl;
  480.                 cerr << resSlow << endl;
  481.                 cerr << n << " " << W << " " << H << endl;
  482.                 for (int i = 0; i < n; ++i) {
  483.                     cerr << motos[i].startPoint.x << " " << motos[i].startPoint.y << " " << motos[i].dir.x << " " << motos[i].dir.y << endl;
  484.                 }
  485.                 break;
  486.             }
  487.         }
  488.         cerr << "OK" << endl;
  489.         return 0;
  490.     }
  491.  
  492.     //{
  493.     //  Point s1(-9000, -5200);
  494.     //  Point d1(7.613, -4.7);
  495.     //  Point s2(-4000, -8000);
  496.     //  Point d2(7.8, -6);
  497.     //  Point e1 = s1 + d1;
  498.     //  Point e2 = s2 + d2;
  499.     //  cerr.precision(20);
  500.     //  cerr << ((e1 - s1) % (s2 - s1)) << endl;
  501.     //  return 0;
  502.     //}
  503.     freopen("j4.in", "rt", stdin);
  504.     freopen("j4.out", "wt", stdout);
  505.  
  506.     int n = nextInt();
  507.     double W = nextDouble();
  508.     double H = nextDouble();
  509.     vector<Moto> motos(n);
  510.     for (int i = 0; i < n; ++i) {
  511.         motos[i] = nextMoto(i);
  512.     }
  513.     double res = solve(W, H, motos);
  514.     //double resSlow = solveSlow(W, H, motos);
  515.     //cerr << res << endl;
  516.     //cerr << resSlow << endl;
  517.     if (!(res >= 0)) {
  518.         throw 0;
  519.     }
  520.     printf("%.12lf\n", res / 1000);
  521.     return 0;
  522. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!