Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const double PI = acos(-1);
- const double EPS = 1e-6;
- double get_angle_of_v(double dx, double dy) {
- double phi = atan2(dy, dx);
- if (phi < 0) {
- phi += 2*PI;
- }
- return phi/PI*180;
- }
- struct Line {
- double k;
- double b;
- double operator() (double const x) {
- return k*x+b;
- }
- double intersect_x (const Line& other) {
- return (other.b-this->b)/(this->k-other.k);
- }
- double angle() const {
- return get_angle_of_v(1, k);
- }
- };
- struct Point {
- double x;
- double y;
- };
- struct Segment {
- Point one;
- Point two;
- double angle() const {
- double dx = two.x-one.x;
- double dy = two.y-one.y;
- return get_angle_of_v(dx, dy);
- }
- };
- void solve() {
- mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
- ll nvm = rng() % 10000 + 1;
- const double sin_rot = sin(nvm);
- const double cos_rot = cos(nvm);
- auto rotate_everything = [&] (double& x, double& y) -> void {
- double nwx = x * cos_rot - y * sin_rot;
- double nwy = x * sin_rot + y * cos_rot;
- x = nwx;
- y = nwy;
- };
- //ifstream cin("snow.in");
- //ofstream clog("snow.out");
- double streetx1, streety1, streetx2, streety2;
- cin >> streetx1 >> streety1 >> streetx2 >> streety2;
- rotate_everything(streetx1, streety1);
- rotate_everything(streetx2, streety2);
- double main_dx = streetx2-streetx1;
- double main_dy = streety2-streety1;
- Line main = {main_dy/main_dx, 0};
- main.b += streety1-main(streetx1);
- clog << "main: " << main.k << "x + " << main.b << "\n";
- ll n; cin >> n;
- vector<Point> dots(n);
- vector<Segment> poly(n);
- for (ll i = 0; i < n; i += 1) {
- double x, y; cin >> x >> y;
- rotate_everything(x, y);
- dots[i].x = x;
- dots[i].y = y;
- }
- for (ll i = 0; i < n; i += 1) {
- poly[i].one.x = dots[i].x;
- poly[i].one.y = dots[i].y;
- poly[i].two.x = dots[(i+1)%n].x;
- poly[i].two.y = dots[(i+1)%n].y;
- }
- ll moves; cin >> moves;
- vector<Point> movedxdy(moves);
- for (ll i = 0; i < moves; i += 1) {
- double vx, vy;
- cin >> vx >> vy;
- rotate_everything(vx, vy);
- movedxdy[i].x = vx;
- movedxdy[i].y = vy;
- }
- double dx = 0, dy = 0;
- struct Event {
- double x;
- bool erase;
- auto operator<(const Event& other) const {
- return this->x < other.x;
- };
- };
- multiset<Event> events;
- auto find_intersections = [&] () -> void {
- // поиск касательной параллельной вектору
- clog << "dx = " << dx << "\n";
- clog << "dy = " << dy << "\n";
- double move_angle1 = get_angle_of_v(dx, dy);
- double move_angle2 = get_angle_of_v(dx, dy)+180.;
- if (move_angle2 >= 360.) move_angle2 -= 360.;
- clog << "move_angle1: " << move_angle1 << "\n";
- clog << "move_angle2: " << move_angle2 << "\n";
- clog << "points: " << "\n";
- for (const auto &dot : dots) {
- clog << dot.x << " " << dot.y << "\n";
- }
- auto sort_deg = poly;
- sort(sort_deg.begin(), sort_deg.end(), [&] (Segment a, Segment b) {return a.angle() < b.angle();});
- clog << "sorted by degree:\n";
- for (const auto &x : sort_deg) {
- clog << x.one.x << "," << x.one.y << " " << x.two.x << "," << x.two.y << ": " << x.angle() << "\n";
- }
- Segment direct = {{0, 0}, {dx, dy}};
- Segment inverse = {{0, 0}, {-dx, -dy}};
- if (abs(direct.angle()-main.angle()) < EPS || abs(inverse.angle()-main.angle()) < EPS) {
- clog << "Goes in parallel!\n";
- for (const auto &[x, y] : dots) {
- if (abs(main(x)-y) < EPS) {
- clog << "Found on main line: " << x << " " << y << "\n";
- events.insert({min(x, x+dx), 0});
- events.insert({max(x, x+dx), 1});
- }
- }
- return;
- }
- clog << "angle target #1: " << direct.angle() << "\n";
- clog << "angle target #2: " << inverse.angle() << "\n";
- auto it_dir = lower_bound(sort_deg.begin(), sort_deg.end(), direct, [] (Segment a, Segment b) {return a.angle() < b.angle();});
- auto it_inv = lower_bound(sort_deg.begin(), sort_deg.end(), inverse, [] (Segment a, Segment b) {return a.angle() < b.angle();});
- if (it_dir == sort_deg.end()) {
- it_dir = sort_deg.begin();
- }
- if (it_inv == sort_deg.end()) {
- it_inv = sort_deg.begin();
- }
- clog << it_dir->one.x << ";" << it_dir->one.y << "\n";
- clog << it_inv->one.x << ";" << it_inv->one.y << "\n";
- Line kas_dir = {double(dy)/dx, 0};
- kas_dir.b += double(it_dir->one.y) - kas_dir(it_dir->one.x);
- Line kas_inv = {double(dy)/dx, 0};
- kas_inv.b += double(it_inv->one.y) - kas_inv(it_inv->one.x);
- double xx = kas_dir.intersect_x(main);
- double xxx = kas_inv.intersect_x(main);
- if (xx > xxx) {
- swap(xx, xxx);
- }
- events.insert({xx, 0});
- events.insert({xxx, 1});
- clog << "y = " << kas_dir.k << "x + " << kas_dir.b << "\n";
- clog << "y = " << kas_inv.k << "x + " << kas_inv.b << "\n";
- clog << xx << " -> " << xxx << "\n";
- };
- for (ll mvdxdy = 0; mvdxdy < moves; mvdxdy += 1) {
- dx = movedxdy[mvdxdy].x;
- dy = movedxdy[mvdxdy].y;
- find_intersections();
- for (ll i = 0; i < n; i += 1) {
- dots[i].x += dx;
- dots[i].y += dy;
- }
- for (ll i = 0; i < n; i += 1) {
- poly[i].one.x += dx;
- poly[i].two.x += dx;
- poly[i].one.y += dy;
- poly[i].two.y += dy;
- }
- }
- double ans = 0;
- ll curr_active = 0;
- const double ZERO = 798464.1254;
- double last = ZERO;
- while (!events.empty()) {
- auto event = events.begin();
- double x = event->x;
- if (curr_active > 0 && last != ZERO) {
- clog << last << " ----> " << x << "\n";
- ans += x-last;
- }
- last = x;
- bool erase = event->erase;
- events.erase(event);
- curr_active += !erase;
- curr_active -= erase;
- assert(curr_active >= 0);
- }
- assert(curr_active == 0);
- double DX = ans;
- double DY = main.k*DX;
- ans = sqrtl((DX)*(DX)+DY*(DY));
- cout << ans << endl;
- }
- int main() {
- clog << fixed << setprecision(6);
- cout << fixed << setprecision(10);
- ll tt = 1;
- while (tt--)
- solve();
- return 0;
- }
Advertisement
Comments
-
- Когда он пересекает линию не полностью (во время хода) или когда стартует задевая линию - не работает
Add Comment
Please, Sign In to add comment
Advertisement