### baukaman's blog

By baukaman, 11 years ago,

Hardly worked on the following problem(statement in russian, registration is required) but without any success, help plz:

On positive axis (x>0,y>0) Given N blue triangles and M red points. Triangles have one property: they share common vertex at [0,0].

For each triangle we must determine is there at least on red point inside it.

Constraints:
- coordinates are integers between (0,10^9]
- N<=10^5
- M<=10^5
- TL = 2sec

I understand some sort of optimization needed : sweep line or segment tree, but I couldn't figure it out

Do you know how to solve or link to the similiar problems. I would really appreciate.

• +17

By baukaman, 11 years ago,

Hello Codeforces community!

I would like to raise a question about masters degree. Do we really need it? Some people claim that we need it only if we're planning to be a teacher at universities or to continue the science path.

For me it is choise between time and diploma[which I don't know will it be of some use in any way]. If I'm going to apply I will contribute 6pm-10pm time every working day , 9 am-3pm on Saturdays, during 1 year, but with diploma in the end. [+ participation to ACM, but I doubt it, since I'm noob]

On the other hand, I may benefit more on my own studying\contesting\projecting\resting etc.

• +3

By baukaman, 11 years ago,

This problem is a very beautiful one. Thanks to kattis we can solve it. Direct link to the problem. The problem statement is easy.

I got WA on test 2. My approach is: take number(initially equal to 1) multply it to current prime or next prime. (which we keep track of). Number of this operations is bounded. (~ 3000000 possibilities). And we can apply some greedy. In doing above we ensure that previous primes count is not less than current. So in factorization we will have more 2's than 3, more 3's than 5 etc.

Once we have some combinations of primes we use formula: S! / (s1! * s2! *s3! *...*sk! ) for example number of different permutationos of number 2*2*2*3*3 is 5!/(3!*2!).

finally, answer. We are given 1000 numbers to handle. We just memorise it in some set and try to find the answers.