vlecomte's blog

Geometry Special 2018: Editorial
By vlecomte, history, 7 years ago, In English

Hi Codeforces,

I hope you enjoyed the contest despite the difficulty. Do not hesitate to ask questions and discuss the problems here. :)

If you participated, I would really appreciate if you could fill in this short form. It only takes 1 minute and will be useful for my thesis. https://goo.gl/forms/XPfkoRxRjEKmTDt32

Editorial: https://vlecomte.github.io/set/geo18/editorial.pdf

Example solutions:

You can also download all solutions/generators/checkers/validators here: https://vlecomte.github.io/set/

Thanks to all who participated! :)

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

»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

It seems that I approached B in more geometrical rather than formulae way. I reduced this problem to such one:
We are given two lines k, l in 2D rotating with equal speed around some points A, B (possibly in different directions). There is also third line m. Print first time when k, l meet on m.

Assume that they rotate in same direction. Then oriented angle they form is constant, so locus of their intersection is circle containing A, B and an their point of intersection in an arbitrary time (I chose this moment to be 123 to avoid case when this point coincides with A or B). We need to intersect this circle with m and we get at most two candidates for a meeting point and we can choose best one. If they rotate in different directions we can reflect k and A with respect to m and reduce problem to first case.

Always a satisfying thing to crack an involved geo problem :D.

(Btw I forgot to set my alarm and I woke up at 11:30AM and contest was going on from 10AM :().

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Woah, I love that approach! Indeed, when I saw your submission I really wondered what was going on there. :)

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Note that we don’t care about the times when cot t doesn’t exist, that is, t = kπ, since the lasers are guaranteed not to touch at the start.

Too bad, I used tan instead of cot and didn't check if the answer is π / 2.

I got wa 27 because of epsilons and expected all such stupid bugs to fail before that. :(

→ Reply
»
6 months ago, # |
  Vote: I like it +7 Vote: I do not like it

why i can't access the editorial link? It seems to have been deleted.

→ Reply