Hello

Having *n* points in the plane with the property that any 3 of them are collinear, how can I add point to it and maintain this property?

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

1 | Um_nik | 3459 |

2 | tourist | 3438 |

3 | maroonrk | 3359 |

4 | ecnerwala | 3347 |

5 | Benq | 3317 |

6 | ksun48 | 3309 |

7 | boboniu | 3300 |

8 | Petr | 3293 |

9 | Radewoosh | 3289 |

10 | TLE | 3223 |

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

1 | Errichto | 206 |

2 | Monogon | 195 |

3 | SecondThread | 191 |

4 | pikmike | 187 |

5 | antontrygubO_o | 185 |

6 | vovuh | 184 |

7 | Ashishgup | 182 |

8 | Um_nik | 181 |

9 | Radewoosh | 169 |

10 | pashka | 167 |

Hello

Having *n* points in the plane with the property that any 3 of them are collinear, how can I add point to it and maintain this property?

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/24/2020 15:28:52 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

If "any 3 of them are collinear" then they all belong to the same line. Every time you add a point to the set, check if it belongs to the same line. The general equation of the straight line is

ax+by=c. These 3 coefficients are determined by the initial two points in the set. Then a point suffices the collinearity property if the equation still holds when you plug in its coordinates.O(1) insertion time.If, on the other hand, neither of them belong to the same line; you can compute all the lines that pass through that new point and then check that no two of them are coincident. This would have a complexity of

O(n) orO(n·logn) per insertion if you use hash or map respectively. This is probably much slower than what you originally intended but I can't think of any other solution (maybe some approximation algorithm?). Anyway, it's a good starting point for those who are unfamiliar with the topic.