Intersection
时间限制:C/C++/Rust/Pascal 3秒,其他语言6秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

Given n circles in a plane, you need to draw a circle, and find the maximum number of given circles it can intersect with.
Two circles intersect with each other if and only if they share at least one common point. It is guaranteed that any two given circles do not share a common point and do not contain each other. The circle you draw may degenerate into a line (a circle with infinite radius) or a point.

输入描述:

The first line contains an integer n\ (1\leq n\leq 150), indicating the number of circles.
Each of the next n lines contains three integers x_i,y_i\ (|x_i|,|y_i| \leq 10^3) and r_i\ (1 \leq r_i \leq 10^3), indicating the coordinates and the radius of a circle.

输出描述:

Output an integer indicating the maximum number of intersected circles.
示例1

输入

复制
4
-3 1 1
6 0 2
0 -4 2
1 0 1

输出

复制
3
示例2

输入

复制
5
1 4 1
-1 2 1
1 0 1
-1 -2 1
1 -4 1

输出

复制
5