Preparing NOJ

D - 齿轮

1000ms 65536K

Description:

    Rainbow来到一个奇妙的王国,这里有一个奇妙的大门,打开大门,就可以得到其中的宝藏。

    门上面有N个齿轮,若第N个齿轮转动,大门就会打开,第一个齿轮接上了一个动力装置,可以不停转动,可是不妙的是,齿轮系统似乎卡住了,使得第N个齿轮无法转动。

    Rainbow可以拆除系统中的一个齿轮,使大门打开,他希望你能够帮助他找到一个可以让大门打开的拆除方法。


Input:

   第一行一个整数N(1<=N<=1000),表示齿轮的个数。

    接下来有N行。

    第i+1行含有3个实数:xi,yi,ri(-10000<=xi,yi<=10000,0<ri<=10000),表示第i个齿轮的坐标位置为(xi,yi),齿轮半径为ri。

    两个齿轮相切即表示他们相互咬合,保证没有重叠的齿轮。

    注意,计算精度误差设为10e-6。


Output:

 去除的齿轮的编号,若是不可能达成,则输出-1。若不用去除齿轮亦正常运行,输出0,多种方案输出最大的编号。

Sample Input:

3
0.0 0.0 1.0
2.0 0.0 1.0
1.0 1.7320508 1.0

Sample Output:

2

Note:

undefined

本题由旧版NOJ导入,来源:NJU 7th ACM contest

Info

NOJ

Provider NOJ

Code NOJ1158

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet