1519: Hilbert Curve Intersections
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
输入
Input consists of one to 100 data sets, one per line, followed by a final line containing only 0. Each data set consists of four integers separated by blanks in the form
n x1 x2 y
which represents Hn and the segment from (x1/2n, y/2n) to (x2/2n, y/2n), where 0 < n < 31, x1 < x2, and each of x1, x2, and y lie in the range 0 to 2n, inclusive.
输出
The output is one integer per line for each data set: the number of intersections of Hn with the segment. Caution: A brute force solution that computes each intersection individually will not finish within the one minute time limit. As you can see below, there may be more than one billion intersections for any data set.
样例输入 复制
3 2 7 7
4 0 16 1
30 1 1073741823 1
0
样例输出 复制
3
16
1073741822