StefanSebez's blog

mixtrilinear for ioi
By StefanSebez, history, 3 months ago, In English

do i need mixtrilinear for ioi

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

»
3 months ago, # |
  Vote: I like it +83 Vote: I do not like it

Yes. You also need O(N) polygon triangulation, Voronoi diagram, Euler's theorem, Delaunay triangulation, Complex numbers in geometry, Convex hull in 3d, Other Euler's theorem, TSP in polynomial complexity, Planar graphs, Linear algebra in geometry, Another Euler's theorem, FFT, Bentley Ottmann algorithm, Linear time planarity check, Check if set has 3 collinear points in O(N log^3 N), Linear programming in 3/4 dimensions, a few more Euler's theorems and many more geometry algorithms.

As we all know, geometry is super common at IOI so it's important to know it really well. If you think you are good with basic geometry, you're very wrong.

Note
→ Reply
»
3 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Yes

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

If you haven't heard of the Humpty, Dumpty, Queue and Sharky-devil points by age 13 you have no chance at solving an IOI Geometry problem.

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

Of course, you also need everything NemanjaSo2005 said and the optimizations from this goated blog

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it -56 Vote: I do not like it

    You also need to know Miloš tree for processing 2d/3d points online in O(sqrt(n/log)*poly)/O(sqrt(n^(3/2)/log)*poly)

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +132 Vote: I do not like it

      Becoming red doesn't mean you are able to write nonsense now

      → Reply
»
3 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Christ is King

→ Reply