How to solve this problem?

Given n points in a plane and q queries in each query a point P is given, and for each query we have to find the minimum of the dot product of point P taken with the given n points.

1 <= n,q <= 10^5

0 <= |x|,|y| <= 10^9

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

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

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

1 | Errichto | 200 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 184 |

4 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 180 |

8 | Radewoosh | 173 |

9 | SecondThread | 172 |

10 | McDic | 161 |

How to solve this problem?

Given n points in a plane and q queries in each query a point P is given, and for each query we have to find the minimum of the dot product of point P taken with the given n points.

1 <= n,q <= 10^5

0 <= |x|,|y| <= 10^9

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/07/2020 16:05:51 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

It can be solved with convex hull trick. For a fixed point, try to rearrange the formula to make it work.

It looks to me like a 3D convex hull. How do you rearrange it?

First of all, we find lower convex envelope. Then we can run ternary search. It's the simplest way to do it. For max you would find upper convex envelope instead. If constraints would allow coordinates to be negative you would split points by their x(<0 and >=0) and do two queries.

Try problem squad from function cup 2019 it uses this concept but is a bit harder.

X1*x2+y1*y2=sqrt(x1^2+y1^2)*sqrt(x2^2+y2^2)*cos(a)

a is angle between vectors (x1, y1) and (x2, y2). |(x1,y1)|*|(x2,y2)| * cos(a) = (projectio)^2

This can be done with convex hull of dots and some binary search(lower hull for P.y>0 and upper hull for P.y<0)

P.s sorry for my poor english

I know a trendy question on this concept. ;)

It’s surprising how little the word “trendy” describes itself.