# Collision Detection

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1207    Accepted Submission(s): 367

Problem Description
In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given objects. Collision detection algorithms are a basic component of 3D video games. Without them, characters could go through walls and other obstacles.
Here comes an interesting problem, given a ball and a cuboid, you need to detect whether they collide. We say that two objects collide if and only if they share at least one point.

Input
The first line of input is the number of test cases.
Each test case contains two lines, the first line contains 24 integers X1, Y1, Z1, …, X8, Y8, Z8, representing the 8 vertexes of the cuboid. Vertexes are given in random order and you can make sure that all edges of the cuboid are parallel to coordinate axes; the second line contains 4 integers X,Y,Z,R representing the central point of the ball and its radius. All integers given are non-negative and will be less than 100000.

Output
For each case output “Yes” Or “No” on a single line.

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

Sample Output
Yes
No

Source

Recommend
lcy   |   We have carefully selected several similar problems for you:  2437 2429 2433 2435 2428

## 离散化的三种方法（转载）

n棵树依次排好，每棵树都有一个高度，树的顶端有一只鸟。

1  stl去重+set版：

1. #include
2. #include
3. #include
4. #include
5. #include
6. #define MAXN  100050
7. using namespace std;
8. int h[MAXN];
9. int q[MAXN];
10. int s[MAXN*2];
11. set<int>ans[MAXN*2];
12. int main()
13. {
14.     int n,m,cnt;
15.     while(~scanf(“%d%d”,&n,&m))
16.     {
17.         cnt=0;
18.         for(int i=0;i
19.         {
20.             scanf(“%d”,&h[i]);
21.             s[cnt++]=h[i];
22.         }
23.         for(int j=0;j
24.         {
25.             scanf(“%d”,&q[j]);
26.             s[cnt++]=q[j];
27.         }
28.         sort(s,s+cnt);
29.         cnt=unique(s,s+cnt)-s;
30.         for(int i=0;i
31.             ans[i].clear();
32.         for(int i=0;i
33.         {
34.             int d=lower_bound(s,s+cnt,h[i])-s;
35.             ans[d].insert(i+1);
36.         }
37.         for(int j=0;j
38.         {
39.             int d=lower_bound(s,s+cnt,q[j])-s;
40.             if(ans[d].empty())
41.                 printf(“-1n”);
42.             else
43.             {
44.                 printf(“%dn”,*ans[d].begin());
45.                 ans[d].erase(ans[d].begin());
46.             }
47.         }
48.     }
49.     return 0;
50. }

1. #include
2. #include
3. #include
4. #include
5. #include
6. using namespace std;
7. #define maxn  100010
8. struct H
9. {
10.     int v,id;
11. }num[2*maxn];
12.
13. int w[2*maxn];
14. int vis[maxn<<1];
15.
16. bool cmp(H a,H b)
17. {
18.     return a.v
19. }
20. vector <int> vc[maxn<<1];
21.
22. int main()
23. {
24.     int n,m;
25.     int cnt;
26.     while(~scanf(“%d%d”,&n,&m)){
27.         cnt=0;
28.         for(int i=0;i
29.         {
30.             int xx;
31.             scanf(“%d”,&xx);
32.             num[i].v=xx;num[i].id=i;
33.         }
34.         for(int i=n;i
35.         {
36.             int xx;scanf(“%d”,&xx);
37.             num[i].v=xx;num[i].id=i;
38.         }
39.         sort(num,num+n+m,cmp);
40.         int tot=0;w[num[0].id]=0;
41.         for(int i=1;i
42.         {
43.             if(num[i].v==num[i-1].v){
44.                 w[num[i].id]=tot;
45.             }
46.             else w[num[i].id]=++tot;
47.         }
48.         memset(vis,0,sizeof(vis));
49.         for(int i=0;i
50.         {
51.             vis[w[i]]++;vc[w[i]].push_back(i+1);
52.         }
53.         for(int i=n;i
54.         {
55.             if(vis[w[i]]>0)
56.             {
57.                 int le=vc[w[i]].size()-vis[w[i]];
58.                 printf(“%dn”,vc[w[i]][le]);
59.                 vis[w[i]]–;
60.             }
61.             else printf(“-1n”);
62.         }
63.     }
64.     return 0;
65. }

set+map:

1. #include
2. #include
3. #include
4. #include
5. #include
6. #include

7. #include
8. #include
9. #include
11. #define LL long long
12. #define maxn 100005
13. using namespace std;
14. set<int>  mp[maxn];
15. map<int,int> c;
16. //http://www.2cto.com/kf/201108/100912.html
17. //http://blog.csdn.net/tyzhaoqi2004/article/details/6882660
18. int main()
19. {
21.    int n,m;
22.    while(scanf(“%d%d”,&n,&m)!=EOF)
23.    {
24.        int i,j,q,x,t=0;
25.        for(i=1;i<=n;i++)
26.         mp[i].clear();
27.         c.clear();
28.        for(i=0;i
29.        {
30.           scanf(“%d”,&x);
31.           if(!c[x])c[x]=++t;
32.           mp[c[x]].insert(i+1);
33.
34.          // cout<
35.        }
36.        //for(i=1;i<=t;i++)cout<
37.     //   cout<
38.        for(i=0;i
39.        {
40.           scanf(“%d”,&q);
41.           if(mp[c[q]].size()==0)
42.           {
43.              printf(“-1n”);
44.           }
45.           else
46.           {
47.             //  cout<
48.              printf(“%dn”,*(mp[c[q]].begin()));
49.              mp[c[q]].erase(mp[c[q]].begin());
50.             // cout<
51.           }
52.        }
53.
54.     }
55. }

# Gunner II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1433    Accepted Submission(s): 540

Problem Description

Long long ago, there was a gunner whose name is Jack. He likes to go hunting very much. One day he go to the grove. There are n birds and n trees. The i-th bird stands on the top of the i-th tree. The trees stand in straight line from left to the right. Every tree has its height. Jack stands on the left side of the left most tree. When Jack shots a bullet in height H to the right, the nearest bird which stands in the tree with height H will falls.

Jack will shot many times, he wants to know which bird will fall during each shot.

Input

There are multiple test cases (about 5), every case gives n, m in the first line, n indicates there are n trees and n birds, m means Jack will shot m times.

In the second line, there are n numbers h[1],h[2],h[3],…,h[n] which describes the height of the trees.

In the third line, there are m numbers q[1],q[2],q[3],…,q[m] which describes the height of the Jack’s shots.

Please process to the end of file.

[Technical Specification]

All input items are integers.

1<=n,m<=100000(10^5)

1<=h[i],q[i]<=1000000000(10^9)

Output

For each q[i], output an integer in a single line indicates the id of bird Jack shots down. If Jack can’t shot any bird, just output -1.

The id starts from 1.

Sample Input
5 5
1 2 3 4 1
1 3 1 4 2

Sample Output
1
3
5
4
2

Hint

Huge input, fast IO is recommended.

Source

http://blog.csdn.net/axuan_k/article/details/45954561

# pog loves szh II

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2115    Accepted Submission(s): 609

Problem Description
Pog and Szh are playing games.There is a sequence with

Input
Several groups of data (no more than

Output
For each case,output an integer means the largest score.

Sample Input
4 4
1 2 3 0
4 4
0 0 2 2

Sample Output
3
2

Source

Recommend
hujie   |   We have carefully selected several similar problems for you:  5338 5337 5336 5335 5334

## sgu 455. Sequence analysis （floyd 判圈算法，O(1)空间复杂度求循环节）

#### 455. Sequence analysis

Time limit per test: 1 second(s)
Memory limit: 4096 kilobytes
input: standard
output: standard

Due to the slow ‘mod’ and ‘div’ operations with int64 type, all Delphi solutions for the problem 455 (Sequence analysis) run much slower than the same code written in C++ or Java. We do not guarantee that Delphi solution exists.

You are given a sequence of signed 64-bit integers defined as follows:

• x0 = 1,
• ,

where

mod

is a remainder operator. All arithmetic operations are evaluated without overflow checking. Use standard “remainder” operator for programming languages (it differs from the mathematical version; for example  in programming, while  in mathematics).

Let’s call a sequence element xp repeatable if it occurs later in the sequence — meaning that there exists such qq > p, that xq = xp. The first repeatable element M of the sequence is such an element xmthat xm is repeatable, and none of the xp where p < m are repeatable.

Given AB and C, your task is to find the index of the second occurence of the first repeatable element M in the sequence if the index is less or equal to 2 · 106. Per definition, the first element of the sequence has index 0.

Input

The only line of input contains three signed 64-bit integers: AB and C (B > 0, C > 0).

Output

Print a single integer  — the index of the second occurence of the first repeatable member if it is less or equal to 2 · 106. Print -1 if the index is more than 2 · 106.

Example(s)

Note

In the first sample test the sequence starts with the following numbers: 1, 3, 7, 6, 3, 7. The first repeatable element is 3. The second occurence of 3 has index 4.

In the second sample test the sequence starts with the following numbers: 1, 2305843009213693951, -4611686018427387903, 6917529027641081855, 0, 0, 0. The first repeatable element is 0. The second occurence of 0 has index 5.

In the third sample test the sequence starts with the following numbers: 1, -2, 4, -3, 1, -2, 4. The first repeatable element is 1. The second occurence of 1 has index 4.

http://www.cnblogs.com/oyking/p/4286916.html  这份题解讲得很详细

## sgu 463 – Walking around Berhattan

K – Walking around Berhattan

Time Limit:250MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

Description

As you probably know, Berhattan is a district of Berland’s largest city and it consists of equal square blocks. There are n block lines in the east-west direction and m block lines in the south-north direction. The map shows Berhattan as a rectangle with n rows and mcolumns, so there are nm blocks in total.

There are n+1 streets running parallel in the east-west direction (horizontally), and there are m+1 avenues running parallel in the south-north direction (vertically). Streets and avenues split the district into blocks and separate Berhattan from other districts of Berland. Each block in Berhattan is characterized by its beauty bij.

A pedestrian can walk only along streets and avenues. When the pedestrian walks along any of four sides of a block, we say he passes the block. Every time the pedestrian passes a block his satisfaction is increased by bij. If the pedestrian has already passed the block one or more times his satisfaction is increased only by bij/2 rounded down when he passes the block again.

You are given the map of Berhattan with the information about the blocks’ beauty and the pedestrian’s path along the streets and avenues. The path is given as a string containing letters ‘

‘, ‘

‘ and ‘

‘, where ‘

‘ means a 90 degree left turn, ‘

‘ means a 90 degree right turn, and ‘

‘ means walking one block forward by a street or avenue. Facing the east, the pedestrian starts his path in the north-west corner of Berhattan having zero satisfaction level. His path can cross itself and go along the same streets or avenues several times. Pedestrian’s satisfaction is increased every time he moves according to the rules described above.

Your task is to calculate the total satisfaction the pedestrian will get after finishing his route.

Picture of the sample test

Input

The first line of input contains two integers n and m (1 ≤ nm ≤ 100), where n is a number of block lines in Berhattan running in the east-west direction, and m is a number of block lines in Berhattan running in the south-north direction. The following n lines contain m digits each. The j-th digit of the i-th line represents bij (0 ≤ bij ≤ 9) — the beauty of the corresponding block. The last line of input contains a path in the format specified above. The path consists of 1 up to 500 characters, inclusively. It is guaranteed that the given path doesn’t go outside Berhattan.

Output

Print a single integer to the output — the total pedestrian’s satisfaction.

Sample Input

## SGU 456 Annuity Payment Scheme

D – Annuity Payment Scheme

Time Limit:500MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

Description

At the peak of the Global Economic Crisis BerBank offered an unprecedented credit program. The offering was so attractive that Vitaly decided to try it. He took a loan of s burles for m months with the interest rate of p percent.

Vitaly has to follow the scheme of annuity payments, meaning that he should make fixed monthly payments — x burles per month. Obviously, at the end of the period he will pay m · x burles to the bank in total.

Each of the monthly payments is divided by BerBank into two parts as follows:

• The first part ai is used to pay off the percent p of the current debt. It’s clear that ai=s’ · p / 100 where s‘=s for the first month and equals to the remaining debt for each of the subsequent months.
• The second part bi is used to pay off the current debt. The sum of all bi over the payment period is equal to s, meaning that the borrower needs to pay off the debt completely by decreasing it from s to 0 in m months.

BerBank uses calculations with floating-point numbers, and the value of x is uniquely determined by sm and p

For example, if s=100, m=2, p=50 then x=90. For the first month a1 = s‘ · p / 100 = s · p / 100 = 50 and b1 = 90 – 50 = 40. For the second month a2 = (100-40) · 50 / 100 = 30, so b2 = 90 – 30 = 60 and the debt is paid off completely.

Your task is to help Vitaly and write a program that computes x given the values of sm and p.

Input

The single line of the input contains three integers sm and p (1 ≤ s ≤ 10 6, 1 ≤ m ≤ 120, 0 ≤ p ≤ 100).

Output

Output the single value of monthly payment x in burles. An absolute error of up to 10 -5 is allowed.

Sample Input

no tags

The kids in my son’s kindergarten made Christmas cookies with their teacher, and piled them up in columns.  They then arranged the columns so that the tops of the columns, going from shortest to tallest, were in a nice straight ramp.  The cookies were all of uniform size.  Given that there were A cookies in the shortest pile, that the difference in height between any two adjacent piles was D cookies, and that there were N piles, can you write a program to figure out how many cookies there were in total?

INPUT
The first line contains the number of test cases T. T lines follow, one corresponding to each test case, containing 3 integers : N, A and D.

OUTPUT
Output T lines, each line containing the required answer for the corresponding test case.

CONSTRAINTS
T <= 100
1 <= N, A, D <=100

SAMPLE INPUT

1 1 1
3 5 6
2 1 2

SAMPLE OUTPUT

33

EXPLANATION
In the second test case the sequence is: 5, 11, 17 whose sum is 33.

## poj 2823 Sliding Window (单调队列)

Sliding Window
 Time Limit: 12000MS Memory Limit: 65536K Total Submissions: 46705 Accepted: 13485 Case Time Limit: 5000MS

Description

An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3.

Window position Minimum value Maximum value
[1  3  -1] -3  5  3  6  7  -1 3
1 [3  -1  -3] 5  3  6  7  -3 3
1  3 [-1  -3  5] 3  6  7  -3 5
1  3  -1 [-3  5  3] 6  7  -3 5
1  3  -1  -3 [5  3  6] 7  3 6
1  3  -1  -3  5 [3  6  7] 3 7

Your task is to determine the maximum and minimum values in the sliding window at each position.

Input

The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.

Output

There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.

Sample Input

Sample Output

Source

a)从队头到队尾，元素在我们所关注的指标下是递减的（严格递减，而不是非递增），比如查询如果每次问的是窗口内的最小值，那么队列中元素从左至右就应该递增，如果每次问的是窗口内的最大值，则应该递减，依此类推。这是为了保证每次查询只需要取队头元素。

b)从队头到队尾，元素对应的时刻（此题中是该元素在数列a中的下标）是递增的，但不要求连续，这是为了保证最左面的元素总是最先过期，且每当有新元素来临的时候一定是插入队尾。

POJ2823就是上面描述的那道题。

http://www.cnblogs.com/Jason-Damon/archive/2012/04/19/2457889.html

tle成狗

logn的复杂度总可以了吧啊?

## codeforces 442C. Artem and Array

C. Artem and Array
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Artem has an array of n positive integers. Artem decided to play with it. The game consists of n moves. Each move goes like this. Artem chooses some element of the array and removes it. For that, he gets min(a, b) points, where a and b are numbers that were adjacent with the removed number. If the number doesn’t have an adjacent number to the left or right, Artem doesn’t get any points.

After the element is removed, the two parts of the array glue together resulting in the new array that Artem continues playing with. Borya wondered what maximum total number of points Artem can get as he plays this game.

Input

The first line contains a single integer n (1 ≤ n ≤ 5·105) — the number of elements in the array. The next line contains n integers ai(1 ≤ ai ≤ 106) — the values of the array elements.

Output

In a single line print a single integer — the maximum number of points Artem can get.

Sample test(s)
input

output

input

output

input

output

## cf 442B Andrey and Problem

B. Andrey and Problem
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Andrey needs one more problem to conduct a programming contest. He has n friends who are always willing to help. He can ask some of them to come up with a contest problem. Andrey knows one value for each of his fiends — the probability that this friend will come up with a problem if Andrey asks him.

Help Andrey choose people to ask. As he needs only one problem, Andrey is going to be really upset if no one comes up with a problem or if he gets more than one problem from his friends. You need to choose such a set of people that maximizes the chances of Andrey not getting upset.

Input

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of Andrey’s friends. The second line contains n real numbers pi(0.0 ≤ pi ≤ 1.0) — the probability that the i-th friend can come up with a problem. The probabilities are given with at most 6 digits after decimal point.

Output

Print a single real number — the probability that Andrey won’t get upset at the optimal choice of friends. The answer will be considered valid if it differs from the correct one by at most 10 - 9.

Sample test(s)
input

output

input

output

Note

In the first sample the best strategy for Andrey is to ask only one of his friends, the most reliable one.

In the second sample the best strategy for Andrey is to ask all of his friends to come up with a problem. Then the probability that he will get exactly one problem is 0.1·0.8 + 0.9·0.2 = 0.26.

## cf 443B Kolya and Tandem Repeat

B. Kolya and Tandem Repeat
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Kolya got string s for his birthday, the string consists of small English letters. He immediately added k more characters to the right of the string.

Then Borya came and said that the new string contained a tandem repeat of length l as a substring. How large could l be?

See notes for definition of a tandem repeat.

Input

The first line contains s (1 ≤ |s| ≤ 200). This string contains only small English letters. The second line contains number k (1 ≤ k ≤ 200) — the number of the added characters.

Output

Print a single number — the maximum length of the tandem repeat that could have occurred in the new string.

Sample test(s)
input

output

input

output

input

output

Note

A tandem repeat of length 2n is string s, where for any position i (1 ≤ i ≤ n) the following condition fulfills: si = si + n.

In the first sample Kolya could obtain a string aabaab, in the second — aaabbbbbb, in the third — abracadabrabracadabra.

# Sequence

Accepts: 25

Submissions: 1442
Time Limit: 2000/2000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

## 三角形数_百度百科

x
x　x
x　x　x
x　x　x　x
x　x　x　x x

55、5,050、500,500、50,005,000……都是三角形数。