若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1165: Advanced Causal Measurements (ACM)

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,442

题目描述

Causality is a very important concept in theoretical physics. The basic elements in a discussion of causality are events. An event e is described by its time of occurrence t, and its location, x, and we write e = (t,x). For our concerns, all events happen in the one dimensional geometric space and thus locations are given by a single real number x as a coordinate on x-axis. Usually, theoretical physicists like to define the speed of light to be 1, so that time and space have the same units (actual physical units frighten and confuse theorists).
One event e1 = (t1,x1) is a possible cause for a second event e2 = (t2,x2) if a signal emitted at e1 could arrive at e2. Signals can't travel faster than the speed of light, so this condition can be stated as:
e1 is a possible cause for e2 iff t2 >= t1+|x2-x1|
Thus an event at (-1,1) could cause events at (0,0), (1,2), and (1,3), for example, but could not have caused events at (1,4) or (-2,1). Note that one event can cause several others.
Recently, scientists have observed several unusual events in the geometrically one dimensional universe, and using current theories, they know how many causes were responsible for these observations, but they know nothing about the time and space coordinates of the causes. You asked to write a program to determine the latest time at which the earliest cause could have occurred (i.e. the time such that at least one cause must have occurred on or before this time). Somewhat surprisingly, all the observed events have both space and time coordinates expressed by integer numbers in the range -1000000 ≤ t, x ≤ 1000000.
The figure on the right illustrates the first case from input: the earliest single event as a possible cause of all four events.
The first line of input is the number of cases which follow. Each case begins with a line containing the number n of events and the number m of causes, 1 ≤ n, m ≤ 100000. Next follows n lines containing the t and x coordinates for each event.
Output consists of a single line for each case in the format as in the sample output, giving the latest time at which the earliest cause could have occurred, this will be an integer as our time units are not divisible.

输入

暂无

输出

暂无

样例输入

4
4 1
1 -1
1 3
1 4
2 6
4 2
1 -1
1 3
1 4
2 6
4 3
1 -1
1 3
1 4
2 6
4 4
1 -1
1 3
1 4
2 6

样例输出

Case 1: -2
Case 2: 0
Case 3: 0
Case 4: 1

参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

原站点 Dreams孤独患者 Skip
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist