302045: CF388E. Fox and Meteor Shower

Memory Limit:256 MB Time Limit:6 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Fox and Meteor Shower

题意翻译

## 题目描述 天空中下起了流星雨,且其中有n颗流星。天空可以被看做一个二维的平面,而每颗流星都可以被看做平面上的一点。 小狐狸Ciel看着天空。她发现每颗流星划过天空的轨迹都是一条直线,且每颗流星都以固定的速度运动。Ciel想知道:最多能有几颗流星在一定时间内能与其他流星相遇?(时间范围不限且时间点有可能为负数)流星在处于同一位置时不会相撞。 ## 输入输出格式 ##### 输入格式: 第一行是一个整数n(1<=n<=1000),表示流星的个数。 接下来n行,每行有6个整数:t1,x1,y1,t2,x2,y2——用于描述流星的运动:在t1时,流星的位置为点(x1,y1);在t2时,流星的位置为点(x2,y2)(-10^6<=t1,x1,y1,t2,x2,y2<=10^6; t1≠t1 )。 数据保证不会出现两颗运动轨迹完全相同的流星。 ##### 输出格式: 一个整数——最多能有几颗流星在一定时间内能与其他流星相遇(若没有流星可以相遇,输出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。

题目描述

There is a meteor shower on the sky and there are $ n $ meteors. The sky can be viewed as a 2D Euclid Plane and the meteor is point on this plane. Fox Ciel looks at the sky. She finds out that the orbit of each meteor is a straight line, and each meteor has a constant velocity. Now Ciel wants to know: what is the maximum number of meteors such that any pair met at the same position at a certain time? Note that the time is not limited and can be also negative. The meteors will never collide when they appear at the same position at the same time.

输入输出格式

输入格式


The first line contains an integer $ n $ ( $ 1<=n<=1000 $ ). Each of the next $ n $ lines contains six integers: $ t_{1},x_{1},y_{1},t_{2},x_{2},y_{2} $ — the description of a meteor's orbit: at time $ t_{1} $ , the current meteor is located at the point ( $ x_{1} $ , $ y_{1} $ ) and at time $ t_{2} $ , the meteor is located at point ( $ x_{2} $ , $ y_{2} $ ) ( $ -10^{6}<=t_{1},x_{1},y_{1},t_{2},x_{2},y_{2}<=10^{6}; t_{1}≠t_{2} $ ). There will be no two meteors are always in the same position for any time.

输出格式


Print a single integer — the maximum number of meteors such that any pair met at the same position at a certain time.

输入输出样例

输入样例 #1

2
0 0 1 1 0 2
0 1 0 1 2 0

输出样例 #1

2

输入样例 #2

3
-1 -1 0 3 3 0
0 2 -1 -1 3 -2
-2 0 -1 6 0 3

输出样例 #2

3

输入样例 #3

4
0 0 0 1 0 1
0 0 1 1 1 1
0 1 1 1 1 0
0 1 0 1 0 0

输出样例 #3

1

输入样例 #4

1
0 0 0 1 0 0

输出样例 #4

1

说明

In example 1, meteor 1 and 2 meet in $ t $ =-1 at (0, 0). ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF388E/92f6576946d49d773d48e18d2a63b309435b48b6.png)In example 2, meteor 1 and 2 meet in $ t $ =1 at (1, 0), meteor 1 and 3 meet in $ t $ =0 at (0, 0) and meteor 2 and 3 meet in $ t $ =2 at (0, 1). ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF388E/eea91082e048ed1841de503930c8caae5200c727.png)In example 3, no two meteor meet. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF388E/d3d685e9d1ee252fc27ecc6c07171a89513f7d20.png)In example 4, there is only 1 meteor, and its velocity is zero. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF388E/27d652cd6553596a63b57353a5fcac67067a8305.png)If your browser doesn't support animation png, please see the gif version here: http://assets.codeforces.com/images/388e/example1.gif http://assets.codeforces.com/images/388e/example2.gif http://assets.codeforces.com/images/388e/example3.gif http://assets.codeforces.com/images/388e/example4.gif

Input

题意翻译

## 题目描述 天空中下起了流星雨,且其中有n颗流星。天空可以被看做一个二维的平面,而每颗流星都可以被看做平面上的一点。 小狐狸Ciel看着天空。她发现每颗流星划过天空的轨迹都是一条直线,且每颗流星都以固定的速度运动。Ciel想知道:最多能有几颗流星在一定时间内能与其他流星相遇?(时间范围不限且时间点有可能为负数)流星在处于同一位置时不会相撞。 ## 输入输出格式 ##### 输入格式: 第一行是一个整数n(1<=n<=1000),表示流星的个数。 接下来n行,每行有6个整数:t1,x1,y1,t2,x2,y2——用于描述流星的运动:在t1时,流星的位置为点(x1,y1);在t2时,流星的位置为点(x2,y2)(-10^6<=t1,x1,y1,t2,x2,y2<=10^6; t1≠t1 )。 数据保证不会出现两颗运动轨迹完全相同的流星。 ##### 输出格式: 一个整数——最多能有几颗流星在一定时间内能与其他流星相遇(若没有流星可以相遇,输出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。

加入题单

上一题 下一题 算法标签: