Advertisement
prog3r

2FIX

Dec 11th, 2024 (edited)
48
0
Never
1
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const double PI = acos(-1);
  8. const double EPS = 1e-6;
  9. double get_angle_of_v(double dx, double dy) {
  10.     double phi = atan2(dy, dx);
  11.     if (phi < 0) {
  12.         phi += 2*PI;
  13.     }
  14.     return phi/PI*180;
  15. }
  16.  
  17. struct Line {
  18.     double k;
  19.     double b;
  20.     double operator() (double const x) {
  21.         return k*x+b;
  22.     }
  23.     double intersect_x (const Line& other) {
  24.         return (other.b-this->b)/(this->k-other.k);
  25.     }
  26.     double angle() const {
  27.         return get_angle_of_v(1, k);
  28.     }
  29. };
  30.  
  31. struct Point {
  32.     double x;
  33.     double y;
  34. };
  35.  
  36. struct Segment {
  37.     Point one;
  38.     Point two;
  39.     double angle() const {
  40.         double dx = two.x-one.x;
  41.         double dy = two.y-one.y;
  42.         return get_angle_of_v(dx, dy);
  43.     }
  44. };
  45.  
  46. void solve() {
  47.     mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
  48.     ll nvm = rng() % 10000 + 1;
  49.     const double sin_rot = sin(nvm);
  50.     const double cos_rot = cos(nvm);
  51.     auto rotate_everything = [&] (double& x, double& y) -> void {
  52.         double nwx = x * cos_rot - y * sin_rot;
  53.         double nwy = x * sin_rot + y * cos_rot;
  54.         x = nwx;
  55.         y = nwy;
  56.     };
  57.     //ifstream cin("snow.in");
  58.     //ofstream clog("snow.out");
  59.     double streetx1, streety1, streetx2, streety2;
  60.     cin >> streetx1 >> streety1 >> streetx2 >> streety2;
  61.     rotate_everything(streetx1, streety1);
  62.     rotate_everything(streetx2, streety2);
  63.     double main_dx = streetx2-streetx1;
  64.     double main_dy = streety2-streety1;
  65.     Line main = {main_dy/main_dx, 0};
  66.     main.b += streety1-main(streetx1);
  67.     clog << "main: " << main.k << "x + " << main.b << "\n";
  68.     ll n; cin >> n;
  69.     vector<Point> dots(n);
  70.     vector<Segment> poly(n);
  71.     for (ll i = 0; i < n; i += 1) {
  72.         double x, y; cin >> x >> y;
  73.         rotate_everything(x, y);
  74.         dots[i].x = x;
  75.         dots[i].y = y;
  76.     }
  77.     for (ll i = 0; i < n; i += 1) {
  78.         poly[i].one.x = dots[i].x;
  79.         poly[i].one.y = dots[i].y;
  80.         poly[i].two.x = dots[(i+1)%n].x;
  81.         poly[i].two.y = dots[(i+1)%n].y;
  82.     }
  83.     ll moves; cin >> moves;
  84.     vector<Point> movedxdy(moves);
  85.     for (ll i = 0; i < moves; i += 1) {
  86.         double vx, vy;
  87.         cin >> vx >> vy;
  88.         rotate_everything(vx, vy);
  89.         movedxdy[i].x = vx;
  90.         movedxdy[i].y = vy;
  91.     }
  92.     double dx = 0, dy = 0;
  93.     struct Event {
  94.         double x;
  95.         bool erase;
  96.         auto operator<(const Event& other) const {
  97.             return this->x < other.x;
  98.         };
  99.     };
  100.     multiset<Event> events;
  101.     auto find_intersections = [&] () -> void {
  102.         // поиск касательной параллельной вектору
  103.         clog << "dx = " << dx << "\n";
  104.         clog << "dy = " << dy << "\n";
  105.         double move_angle1 = get_angle_of_v(dx, dy);
  106.         double move_angle2 = get_angle_of_v(dx, dy)+180.;
  107.         if (move_angle2 >= 360.) move_angle2 -= 360.;
  108.         clog << "move_angle1: " << move_angle1 << "\n";
  109.         clog << "move_angle2: " << move_angle2 << "\n";
  110.         clog << "points: " << "\n";
  111.         for (const auto &dot : dots) {
  112.             clog << dot.x << " " << dot.y << "\n";
  113.         }
  114.         auto sort_deg = poly;
  115.         sort(sort_deg.begin(), sort_deg.end(), [&] (Segment a, Segment b) {return a.angle() < b.angle();});
  116.         clog << "sorted by degree:\n";
  117.         for (const auto &x : sort_deg) {
  118.             clog << x.one.x << "," << x.one.y << " " << x.two.x << "," << x.two.y << ": " << x.angle() << "\n";
  119.         }
  120.         Segment direct = {{0, 0}, {dx, dy}};
  121.         Segment inverse = {{0, 0}, {-dx, -dy}};
  122.         if (abs(direct.angle()-main.angle()) < EPS || abs(inverse.angle()-main.angle()) < EPS) {
  123.             clog << "Goes in parallel!\n";
  124.             for (const auto &[x, y] : dots) {
  125.                 if (abs(main(x)-y) < EPS) {
  126.                     clog << "Found on main line: " << x << " " << y << "\n";
  127.                     events.insert({min(x, x+dx), 0});
  128.                     events.insert({max(x, x+dx), 1});
  129.                 }
  130.             }
  131.             return;
  132.         }
  133.         clog << "angle target #1: " << direct.angle() << "\n";
  134.         clog << "angle target #2: " << inverse.angle() << "\n";
  135.         auto it_dir = lower_bound(sort_deg.begin(), sort_deg.end(), direct, [] (Segment a, Segment b) {return a.angle() < b.angle();});
  136.         auto it_inv = lower_bound(sort_deg.begin(), sort_deg.end(), inverse, [] (Segment a, Segment b) {return a.angle() < b.angle();});
  137.         if (it_dir == sort_deg.end()) {
  138.             it_dir = sort_deg.begin();
  139.         }
  140.         if (it_inv == sort_deg.end()) {
  141.             it_inv = sort_deg.begin();
  142.         }
  143.         clog << it_dir->one.x << ";" << it_dir->one.y << "\n";
  144.         clog << it_inv->one.x << ";" << it_inv->one.y << "\n";
  145.  
  146.         Line kas_dir = {double(dy)/dx, 0};
  147.         kas_dir.b += double(it_dir->one.y) - kas_dir(it_dir->one.x);
  148.  
  149.         Line kas_inv = {double(dy)/dx, 0};
  150.         kas_inv.b += double(it_inv->one.y) - kas_inv(it_inv->one.x);
  151.  
  152.         double xx = kas_dir.intersect_x(main);
  153.         double xxx = kas_inv.intersect_x(main);
  154.         if (xx > xxx) {
  155.             swap(xx, xxx);
  156.         }
  157.         events.insert({xx, 0});
  158.         events.insert({xxx, 1});
  159.         clog << "y = " << kas_dir.k << "x + " << kas_dir.b << "\n";
  160.         clog << "y = " << kas_inv.k << "x + " << kas_inv.b << "\n";
  161.         clog << xx << " -> " << xxx << "\n";
  162.     };
  163.     for (ll mvdxdy = 0; mvdxdy < moves; mvdxdy += 1) {
  164.         dx = movedxdy[mvdxdy].x;
  165.         dy = movedxdy[mvdxdy].y;
  166.         find_intersections();
  167.         for (ll i = 0; i < n; i += 1) {
  168.             dots[i].x += dx;
  169.             dots[i].y += dy;
  170.         }
  171.         for (ll i = 0; i < n; i += 1) {
  172.             poly[i].one.x += dx;
  173.             poly[i].two.x += dx;
  174.             poly[i].one.y += dy;
  175.             poly[i].two.y += dy;
  176.         }
  177.     }
  178.     double ans = 0;
  179.     ll curr_active = 0;
  180.     const double ZERO = 798464.1254;
  181.     double last = ZERO;
  182.     while (!events.empty()) {
  183.         auto event = events.begin();
  184.         double x = event->x;
  185.         if (curr_active > 0 && last != ZERO) {
  186.             clog << last << " ----> " << x << "\n";
  187.             ans += x-last;
  188.         }
  189.         last = x;
  190.         bool erase = event->erase;
  191.         events.erase(event);
  192.         curr_active += !erase;
  193.         curr_active -= erase;
  194.         assert(curr_active >= 0);
  195.     }
  196.     assert(curr_active == 0);
  197.     double DX = ans;
  198.     double DY = main.k*DX;
  199.     ans = sqrtl((DX)*(DX)+DY*(DY));
  200.     cout << ans << endl;
  201. }
  202.  
  203. int main() {
  204.     clog << fixed << setprecision(6);
  205.     cout << fixed << setprecision(10);
  206.     ll tt = 1;
  207.     while (tt--)
  208.         solve();
  209.     return 0;
  210. }
  211.  
Advertisement
Comments
  • prog3r
    85 days
    # text 0.18 KB | 0 0
    1. Когда он пересекает линию не полностью (во время хода) или когда стартует задевая линию - не работает
Add Comment
Please, Sign In to add comment
Advertisement