Skip to main content

1185. Wall Timus Online Judge

The problem states that, A greedy king wants to build a wall around his castle with minimum cost and wall should not come closer to the castle than a certain distance.

Given N Cartesian 2D points and minimum distance between castle and wall is L. 

To solve the problem , At first I build a convex hull using the points . 
The wall should be L distance from castle . So, we need another 4 * acos(0.0) * L length ( Summing up all round length of each point of the convex hull ) . 

Problem :: Wall 
Labels:

Comments

  1. Amartya RoyJune 22, 2020 at 2:25 PM

    4 * acos(0.0) * L
    can you elaborate more about this step ?
    I'm not getting how do you come up with this calculation ?

    ReplyDelete

Post a Comment

Popular posts from this blog

Histogram - LOJ

It's a well-known problem and the well-known solution is using a stack. I tried to solve it by segment tree( iterative version for building tree ) and got TLE. Hope I can optimize the code.  TLE CODE 
Post a Comment
Read more

Checking a fraction x/y contains infinite number of numerals after the decimal point

Infinite fractions \[ \text{When is }\ x \mid y \text{ ?} \ \] x can be represent as \[ {x} = \prod_{i=1}^n p_{i}^{k} \] \[ \text{where}\ p_{i} =\text{ is a prime factor of } {x} \text{ and } {x} \text{ has } {n} \text{ prime factors.} \] \[ \text{Example: }\ {x} = {12} = {2}^{2} \times {3} \] We can represent the y by the same way. x divides y ( x is a divisor of y ) if and only if all prime factors of x are available in y prime factorization and each prime factor (p) power (p^a) in x factorization is less than equal to prime factor (p) power (p^b) in y factorization (a <= b). Or we can say that when GCD(x, y) = x  , x divides y. \[ \text{When is }\ x\nmid y \text{ ?} \ \] y = q * x + r [ where r < x ] When reminder (r) is not equal to 0, y is not divisible by x.  Only when r is not equal to zero there are numbers after the decimal point of fraction p/q. How to get numbers after the decimal point of a fraction ? We recursively do it until MOD = 0. init...
Post a Comment
Read more