i tried to learn this technique from this blog.. but i couldn't understand it clearly from this mentioned site..so need some good blogs on this! you may also add related problems...

thanks in advance!

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

1 | tourist | 3509 |

2 | OO0OOO00O0OOO0O0…O | 3327 |

3 | Um_nik | 3297 |

4 | Syloviaely | 3274 |

5 | LHiC | 3216 |

6 | Petr | 3161 |

7 | Benq | 3130 |

8 | ko_osaga | 3124 |

9 | Swistakk | 3089 |

10 | dotorya | 3060 |

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

1 | Radewoosh | 185 |

2 | rng_58 | 161 |

3 | tourist | 158 |

4 | Petr | 152 |

5 | Swistakk | 150 |

5 | Vovuh | 150 |

7 | csacademy | 147 |

8 | PikMike | 146 |

9 | Errichto | 145 |

9 | Um_nik | 145 |

i tried to learn this technique from this blog.. but i couldn't understand it clearly from this mentioned site..so need some good blogs on this! you may also add related problems...

thanks in advance!

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/20/2018 20:33:07 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|

Before you conduct any further research, I have to warn you that the technique was proven wrong in finding the largest triangle in a convex https://codeforces.com/blog/entry/52341.

thanks for your kind information :)

Maybe is wrong for that problem but is useful and proven truth for other problems, like fartest pair of points on a cloud, polygon width, minkowski sum of polygons, convex hull of two convex polygons, etc.

All this problems turn to be linear with this technique.

I recently solved a problem of fartest pair of point under other metric using rotating calipers

But is good to know problems that cannot be solved that way. Thanks

your(cbosh-calrgauss) mentioned problems can't be solved without this way?? i meant alternate solutions except this technique??

Yeah, result that mostly of that problems can be done in

O(NlgN) orO(Nlg^{2}(N)) time, but with rotating calipers you can archive O(N) time, assuming convex hull is done.It seems not to useful but others solutions depens on binary searches and others things that make the code difficult to implement and rotating calipers take short coding.

yup..got it! thanks frnd!