TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3970
  • Problem
  • P3970占点
    Limits : Time Limit : - MS   Memory Limit : 165536 KB
    Judgment Tips : 1s
    Description

    南开中学有一个很大的操场,上面有n名同学(编号1到n)。我们可以看做一个无限大的平面上有n个坐标点。同学们跑步速度有快有慢。对于操场上的任何一点,如果一个学生能比其他学生都先到达(跑直线,没有人比他先到或同时到),那么这个点就被他占领。 请你计算,哪些同学能占领无穷多个点。

    Input Format

    输入含有多组数据(<=8组),对于每组数据:
        第一行一个整数n。

    接下来n行,每行三个整数x,y,v,按1到n的顺序依次描述一个同学的位置坐标(x,y)和他的跑步速度。

    输入以单独一行,一个数字0作为结束。

    Output Format

    对于每组数据,输出一行,n个数字,对应1到n号学生的情况。如果该学生能占用无限多个点,输出1,否则输出0。

    Sample Input 1

    3
    0 0 3
    1 1 2
    2 2 1
    0

    Sample Output 1

    100

    Sample Input 2

    3
    0 0 2
    1 1 1
    2 0 2
    4
    1 1 3
    1 1 2
    2 2 2
    3 3 1
    0

    Sample Output 2

    101
    1000

    Hint

    对于20%的数据: 1<=n<=5  

    对于100%的数据:1<=n<=500   0<=|x|,|y|,v<=10^4

    来源 hdu 4946


    Source  udh 6494