p150.cpp
======================
#include <bits/stdc++.h>
// #include <coding_library/geometry/point.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

using coord_t = double;

struct Point {
    static constexpr coord_t eps = 1e-9;

    coord_t x, y;
    Point(coord_t x = 0, coord_t y = 0) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(coord_t c) const { return Point(x * c, y * c); }
    Point operator/(coord_t c) const { return Point(x / c, y / c); }

    coord_t operator*(const Point& p) const { return x * p.x + y * p.y; }
    coord_t operator^(const Point& p) const { return x * p.y - y * p.x; }

    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator!=(const Point& p) const { return x != p.x || y != p.y; }
    bool operator<(const Point& p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
    bool operator>(const Point& p) const {
        return x != p.x ? x > p.x : y > p.y;
    }
    bool operator<=(const Point& p) const {
        return x != p.x ? x < p.x : y <= p.y;
    }
    bool operator>=(const Point& p) const {
        return x != p.x ? x > p.x : y >= p.y;
    }

    coord_t norm2() const { return x * x + y * y; }
    coord_t norm() const { return sqrt(norm2()); }
    coord_t angle() const { return atan2(y, x); }

    Point rotate(coord_t a) const {
        return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    Point perp() const { return Point(-y, x); }
    Point unit() const { return *this / norm(); }
    Point normal() const { return perp().unit(); }
    Point project(const Point& p) const {
        return *this * (*this * p) / norm2();
    }
    Point reflect(const Point& p) const {
        return *this * 2 * (*this * p) / norm2() - p;
    }

    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }
    friend istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }

    friend int ccw(const Point& a, const Point& b, const Point& c) {
        coord_t v = (b - a) ^ (c - a);
        if(-eps <= v && v <= eps) {
            return 0;
        } else if(v > 0) {
            return 1;
        } else {
            return -1;
        }
    }

    friend bool point_on_segment(
        const Point& a, const Point& b, const Point& p
    ) {
        return ccw(a, b, p) == 0 && p.x >= min(a.x, b.x) - eps &&
               p.x <= max(a.x, b.x) + eps && p.y >= min(a.y, b.y) - eps &&
               p.y <= max(a.y, b.y) + eps;
    }

    friend bool point_in_triangle(
        const Point& a, const Point& b, const Point& c, const Point& p
    ) {
        int d1 = ccw(a, b, p);
        int d2 = ccw(b, c, p);
        int d3 = ccw(c, a, p);
        return (d1 >= 0 && d2 >= 0 && d3 >= 0) ||
               (d1 <= 0 && d2 <= 0 && d3 <= 0);
    }

    friend Point line_line_intersection(
        const Point& a1, const Point& b1, const Point& a2, const Point& b2
    ) {
        return a1 +
               (b1 - a1) * ((a2 - a1) ^ (b2 - a2)) / ((b1 - a1) ^ (b2 - a2));
    }

    friend bool collinear(const Point& a, const Point& b) {
        return abs(a ^ b) < eps;
    }

    friend Point circumcenter(const Point& a, const Point& b, const Point& c) {
        Point mid_ab = (a + b) / 2.0;
        Point mid_ac = (a + c) / 2.0;
        Point perp_ab = (b - a).perp();
        Point perp_ac = (c - a).perp();
        return line_line_intersection(
            mid_ab, mid_ab + perp_ab, mid_ac, mid_ac + perp_ac
        );
    }
};

int n;
Point a, b;

void read() { cin >> a >> b >> n; }

void solve() {
    // This is a simple problem - we can simply simulate the n steps, by walking
    // with distance 1.0 in the direction to x1,y1. We look at the 9 adjacent
    // cells, and keep a visited map to not over count (or we can just remove
    // the later on). When we get to N points, we will sort them by distance
    // from x1,y1. We have to be careful about precision issues, so we opt for
    // integer computation.

    Point dir = b - a;
    double len = dir.norm();
    constexpr double eps = 1e-9;

    if(len < eps) {
        bool on_boundary =
            abs(a.x - round(a.x)) < eps || abs(a.y - round(a.y)) < eps;
        if(on_boundary || n != 1) {
            cout << "no solution" << endl;
        } else {
            cout << (int)floor(a.x) << " " << (int)floor(a.y) << endl;
        }
        return;
    }

    vector<pair<int, int>> order;
    double dt = 1.0 / len;

    int x1 = (int)a.x, y1 = (int)a.y, x2 = (int)b.x, y2 = (int)b.y;
    int dx = x2 - x1, dy = y2 - y1;

    auto intersects_cell = [&](int ncx, int ncy) -> bool {
        int64_t t_min_num = 0, t_min_den = 1;
        int64_t t_max_num = 1, t_max_den = 1;

        if(dx != 0) {
            int64_t t1_num = ncx - x1, t2_num = ncx + 1 - x1;
            int64_t den = dx;
            if(den < 0) {
                t1_num = -t1_num;
                t2_num = -t2_num;
                den = -den;
            }
            if(t1_num > t2_num) {
                swap(t1_num, t2_num);
            }
            if(t1_num * t_min_den > t_min_num * den) {
                t_min_num = t1_num;
                t_min_den = den;
            }
            if(t2_num * t_max_den < t_max_num * den) {
                t_max_num = t2_num;
                t_max_den = den;
            }
        } else if(x1 <= ncx || x1 >= ncx + 1) {
            return false;
        }

        if(dy != 0) {
            int64_t t1_num = ncy - y1, t2_num = ncy + 1 - y1;
            int64_t den = dy;
            if(den < 0) {
                t1_num = -t1_num;
                t2_num = -t2_num;
                den = -den;
            }
            if(t1_num > t2_num) {
                swap(t1_num, t2_num);
            }
            if(t1_num * t_min_den > t_min_num * den) {
                t_min_num = t1_num;
                t_min_den = den;
            }
            if(t2_num * t_max_den < t_max_num * den) {
                t_max_num = t2_num;
                t_max_den = den;
            }
        } else if(y1 <= ncy || y1 >= ncy + 1) {
            return false;
        }

        return t_min_num * t_max_den < t_max_num * t_min_den;
    };

    auto get_entry_t = [&](int ncx, int ncy) -> double {
        double t_min = 0;
        if(dx != 0) {
            double t1 = (double)(ncx - x1) / dx;
            double t2 = (double)(ncx + 1 - x1) / dx;
            t_min = max(t_min, min(t1, t2));
        }
        if(dy != 0) {
            double t1 = (double)(ncy - y1) / dy;
            double t2 = (double)(ncy + 1 - y1) / dy;
            t_min = max(t_min, min(t1, t2));
        }
        return t_min;
    };

    for(double t = 0; t <= 1.0 + eps && (int)order.size() < 8 * n; t += dt) {
        double x = a.x + dir.x * t;
        double y = a.y + dir.y * t;
        int cx = (int)floor(x);
        int cy = (int)floor(y);

        for(int dcx = -1; dcx <= 1; dcx++) {
            for(int dcy = -1; dcy <= 1; dcy++) {
                int ncx = cx + dcx;
                int ncy = cy + dcy;
                if(intersects_cell(ncx, ncy)) {
                    order.push_back({ncx, ncy});
                }
            }
        }
    }

    sort(order.begin(), order.end(), [&](const auto& a, const auto& b) {
        return get_entry_t(a.first, a.second) < get_entry_t(b.first, b.second);
    });
    order.erase(unique(order.begin(), order.end()), order.end());

    if((int)order.size() < n) {
        cout << "no solution" << endl;
    } else {
        cout << order[n - 1].first << " " << order[n - 1].second << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p150.in1
======================
2 3 4 -1 3


=================
p150.ans1
======================
3 0

=================
statement.txt
======================
150. Mr. Beetle II
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



There is a small beetle living on infinite checkered sheet. Size of each cell is 1x1, the axes of Cartesian coordinate system are lying on the border of cells. Early in the morning beetle travels from his house at point (x1,y1) to the point (x2,y2). All cells that he passed are numbered in order of passing (borders and corners of cells are not considered to be parts of cells). You need to find coordinates of left lower corner of n-th cell on the way of Mr Beetle.

Input
Input consists of integers x1,y1,x2,y2,n (1<=n<=10^5) written in one line. All coordinates are not greater than 10^6 by it's absolute values.

Output
Write two numbers, separated by space: coordinates of left most lower point of n-th cell in the beetle's way. If such cell doesn't exist then write 'no solution'.

Sample test(s)

Input
2 3 4 -1 3

Output
3 0
Author:	Michael R. Mirzayanov
Resource:	Saratov Subregional School Team Contest, 2002
Date:	Spring, 2002

=================
