_Ash__'s blog

By _Ash__, history, 7 months ago, In English,

There are two non-intersecting convex polygon strictly inside a circle. The problem is to draw a line such that the polygons are on the different side of the line , the area of the part containing the first polygon is minimum. The inputs are such that you can always draw such a line. How to solve this problem ? number of points <= 50000

Problem name: circular island Problem link : https://codeforces.com/gym/101370/attachments/download/5499/20092010-summer-petrozavodsk-camp-petr-mitrichev-contest-5-en.pdf

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By _Ash__, history, 7 months ago, In English,

How can I take preparation for attacking computational geometry problems appearing in world finals ? A good set of problems (if possible with solution) would very much help. Thank you

Read more »

 
 
 
 
  • Vote: I like it
  • +58
  • Vote: I do not like it

By _Ash__, history, 11 months ago, In English,

There is a problem from phuket regional 2015 that i have been trying to solve.

Here is the problem link : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=690&page=show_problem&problem=5321

The problem transforms into something like this , there is a tree ( at most 10^5 nodes) where each node has two values(let them call a,b). Now there are some (at most 10^5) queries of form : U V x y .

You have to find all the nodes on path U to V for which a*x + b*y is minimum. Note that if this minimum occurs for several nodes , you have to find them all. It is guaranteed that you don't have to print more than 3*10^5 nodes' id.

Read more »

 
 
 
 
  • Vote: I like it
  • +40
  • Vote: I do not like it