logo AlgoBeat OnlineJudge
登录 注册

#10297. [BalticOI 1995] rectangles 矩形

内存限制:1024 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: AlgoBeat 官方账号

题目描述

早期题目时限较长,卡评测直接封号。

为一个矩形,其顶点坐标为:

称该矩形索引为 1。它的边长比例为 (见图 1)。

第二个矩形(索引 2)建立在第一个矩形的“北”边 上,并保持相同的边长比例
该矩形为 ,满足
此时公共矩形 的“西”边为

第三个矩形建立在边 上,同样保持比例 ,矩形为 ,满足

依此类推,后续矩形依次建立在之前公共矩形的边上,边长比例始终为 ,且基边的方向按顺序循环:
“南”、“东”、“北”、“西”、“南”……

给定整数 ),请找出覆盖点 的矩形的最小索引。
若点 落在边或顶点上,则视为被索引较小的矩形覆盖。

输入格式

输入文件只有一行,包含三个整数 ,之间用单个空格分隔。

输出格式

输出文件只有一行,包含一个整数 —— 最小覆盖索引。

样例

样例输入 #1

3 0 1

样例输出 #1

1

样例输入 #2

2 7 -2

样例输出 #2

5

样例输入 #3

4 1 17

样例输出 #3

2