CF388E Fox and Meteor Shower
题目描述
天空中下起了流星雨,且其中有n颗流星。天空可以被看做一个二维的平面,而每颗流星都可以被看做平面上的一点。
小狐狸Ciel看着天空。她发现每颗流星划过天空的轨迹都是一条直线,且每颗流星都以固定的速度运动。Ciel想知道:最多能有几颗流星在一定时间内能与其他流星相遇?(时间范围不限且时间点有可能为负数)流星在处于同一位置时不会相撞。
输入格式
第一行是一个整数n(1
输出格式
一个整数——最多能有几颗流星在一定时间内能与其他流星相遇(若没有流星可以相遇,输出1)。
说明/提示
样例1中,流星1和流星2在时间点-1于点(0,0)相遇,故有2颗流星可以与其他流星相遇。
样例2中,流星1和流星2在时间点-1于点(1,0)相遇,流星1和流星3在时间点0于点(0.0)相遇,流星2和流星3在时间点2于点(0,1)相遇,故有3颗流星可以与其他流星相遇。
在样例3中,没有流星能与其他流星相遇,故输出1。
在样例4中,只有一颗流星,且速度为0,故输出1。
若你的浏览器不支持动图,请点击以下链接以查看样例示意gif。