There are n boys. All of them are friends. They live in all over the world. One day, one of them wants to know the farthest distance between two boys. Now, you are given the positions of boys. Two boys may in the same position. Your are required to tell boys the farthest distance. Input The first line is one integer n.(1 ≤ n ≤ 105) Each of next n lines has two integers xi and yi, which means the i-th boy's position. (0 ≤ xi, yi ≤ 1010) There are multiple test cases, please stop when n = 0. Output One line for each test case containing a real number in three decimal places.
组合数取模
Long long ago, there was a beautiful boy, he was so lonely in the summer night. At his most lonely moment, he decided to invite his boyfriends to his bedroom, and they will be happy together. The beautiful boy owned n boyfriends,and he would be happy only with exactly m boyfriends in his bedroom. So how many ways he could be happy? As the beautiful boy had too many boyfriends, and he was so lonely, the answer could be very large. You just need give the answer module 10^18+7. Input There are multiple test cases(No more than 66). For each test case: There are two integers n,m (1<=n,m<=10^5) The last line contains two integers: 0 0 Output For each cases,output a line with a integer ,which is the answer module 1e18+7. If the beautiful could never be happy,you can just output his voice from heart: "How lonely night~"(without quotes) Sample Input 3 2 10 5 3 5 0 0 Sample Output 3 252 How lonely night~ Hint For the first case: The beautiful boy had 3 friends :A,B,C He could invite A+B,A+C,B+C. So the answer should be 3 For the third case: The beautiful boy had 3 friends, but he wanted 5 friends,so he would never be happy.(So pity!) '~' is shift+`
SG函数
唉...今天又学习了一下SG函数...都是之前挖的坑QAQ
AC自动机
Recently Peter received m strings as a birthday gift. These strings only consist of lowercase letters. But Peter is not happy, as he hates all of these strings. So he wants to construct a new string of length n and it cannot contain any of the m strings as a substring. Of course,the new string is made up of lowercase letters too. Now he wonders how many strings he can construct. Input On the first line there is only one integer T(T is about 10), representing the number of cases. In each case: there are two integers n, m(n ≤ 1000, m ≤ 50) on the first line followed by m lines, representing the m strings Peter received. Note that the total length of the m strings won’t exceed 500 in each case. Output For each test case, output an integer in one line, which is the number of strings Peter can construct mod 1000000007. Sample Input 1 5 1 aaa Sample Output 11879400