# | User | Rating |
---|---|---|

1 | tourist | 3851 |

2 | jiangly | 3634 |

3 | Um_nik | 3539 |

4 | slime | 3498 |

5 | ksun48 | 3493 |

6 | djq_cpp | 3486 |

7 | maroonrk | 3471 |

8 | Radewoosh | 3442 |

9 | Petr | 3426 |

10 | Isonan | 3344 |

# | User | Contrib. |
---|---|---|

1 | -is-this-fft- | 184 |

2 | awoo | 181 |

3 | dario2994 | 171 |

4 | SecondThread | 169 |

5 | maroonrk | 168 |

5 | Um_nik | 168 |

7 | adamant | 167 |

8 | YouKn0wWho | 166 |

9 | errorgorn | 165 |

10 | antontrygubO_o | 162 |

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/30/2022 09:25:08 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I haven't seen that randomized algo to intersecting halfplanes earlier, but I think it's worth noting that main idea is almost the same as in Smallest Enclosing Circle problem (does there even exist deterministic algo with similar complexity?)

Yes, it's quite similar. I'm surprised you didn't see this one before — I had the feeling of being the last one to the party when I learned about it :)

Maybe that's because I am quite satisfied with online half-planes intersection working in that pompon left in our library :).

Can you please share your library here ?

I think that I know a different solution to the half-plane problem. Instead of doing binary search, let the value gradually decrease and look at the polygon where

Omust be located. Initially, when , this polygon is the same as the input polygon. When the value is decreased, the sides move inwards at constant speed which can be determined in linear time using rotating calipers algorithm. The lengths of the sides decrease linearly, so it is possible to find the times when each length would reach zero. When the length of a side becomes zero, adjacent sides will begin shrinking faster, so it is necessary to emulate this process and to recompute the times for adjacent sides when one of the sides disappears. This can be easily done in time using a heap. So, this solution works in time, doesn't use binary search and is completely deterministic.