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

Gray Code

A Gray code is a list of all 2^n  bit strings of length , where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one).  source   The problem is, how to generate Gray Code for a given length n.  When n = 2 , Gray Code :  00  01  11  10 When n = 3, Gray Code : 000 001 011 010 110 111 101 100 000(0) position Gray code string 000  001(1) -> 001  010(2) -> 011  011(3) -> 010 .....  Key observation -  For the  K position, the Gray code string is S .   if i and (i+1)- th bit of K is equal then i- th char of S will be  ' 0 ', otherwise, it will be ' 1 '.   Code :               int n; cin >> n;     for(int i = 0; i < (1 << n); i++) {         int value =  ( i ^ (i >> 1) ) ;         string s = "";         for(int j = 0; j < n; j++) {             if( value & (1 << j) )s.push_back('1');             else s.push_back('0');         }         reverse( s.begin(), s.end() );      
Post a Comment
Read more

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