编程介的小学生
2018-12-27 17:20
采纳率: 92.6%
浏览 333

是一个记录去重的算法问题,需要使用C语言的思路去解决的办法?

Problem Description
There are two kinds of people.

If person i is the first kind of people, it locates at position (pi, 0) initially, starts moving at time ti with a constant velocity of (0, v1), and then sees every person sits at the line segment (xi, yi), (xi + wi, yi), include the two points, where (xi, yi) is the position of person i at that time and wi is its vision.

If person i is the second kind of people, it locates at position (0, pi) initially, starts moving at time ti with a constant velocity of (v2, 0), and then sees every person sits at the line segment (xi, yi), (xi, yi + wi), include the two points, where (xi, yi) is the position of person i at that time and wi is its vision.

Now given the position of people, please calculate the number of distinct people every person has finally seen.

Input
There are multiply test cases.

The first line contains an integer T(T<=10), indicates the number of cases.

For each test case, the first line contains three integers n, v1, v2(1<=n,v1,v2<=10^5), indicating the total number of two kinds of people, the speed of the first kind, and the speed of the second kind.

Then comes N lines, the i-th line contains four integers ai, ti, pi, wi (1<=ai<=2, 1<=ti,pi,wi<=10^5), describing a person, where ai is the type, ti is time the person starts moving, pi is the location and wi is the vision.

It is granted that for the same kind of people, all ti, pi are different.

Output
For each case, you should output "Case #k:" first, where k indicates the case number and counts from 1.

Then output N lines, each lines is an integer, indicates the number of distinct people the i-th person finally recorded.

Sample Input
1
2 1 1
1 1 1 1
2 2 2 1

Sample Output
Case #1:
1
1

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • threenewbee 2019-08-30 23:42
    已采纳
    已采纳该答案
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题