TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3970
  • 题目
  • P3970占点
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1s
    问题描述

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

    输入格式

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

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

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

    输出格式

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

    样例输入 1

    3
    0 0 3
    1 1 2
    2 2 1
    0

    样例输出 1

    100

    样例输入 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

    样例输出 2

    101
    1000

    提示

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

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

    来源 hdu 4946


    来源  udh 6494