Hey! Does anybody know how to solve this? Given n segments, count how many pairs of segments have a common point. There are no 2 overlapping segments and the segments are can make any angle with the origin of the cartesian plane.

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

1 | tourist | 3624 |

2 | Um_nik | 3468 |

3 | mnbvmar | 3363 |

4 | Petr | 3330 |

5 | wxhtxdy | 3329 |

6 | LHiC | 3300 |

7 | sunset | 3278 |

8 | V--o_o--V | 3275 |

9 | Vn_nV | 3182 |

10 | dotorya | 3156 |

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

1 | Radewoosh | 190 |

2 | Errichto | 185 |

3 | rng_58 | 161 |

3 | PikMike | 161 |

5 | Petr | 156 |

6 | Ashishgup | 153 |

6 | Vovuh | 153 |

8 | neal | 151 |

8 | majk | 151 |

8 | 300iq | 151 |

8 | Um_nik | 151 |

Hey! Does anybody know how to solve this? Given n segments, count how many pairs of segments have a common point. There are no 2 overlapping segments and the segments are can make any angle with the origin of the cartesian plane.

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/26/2019 14:14:28 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

you can do this with a sweepline approach Bentley–Ottmann algorithm

But if number of crossings is big (quadratic, let's say) this algorithms is bad since it explicitly lists all of them and count them one by one. However, I am not sure if the original problem is solvable at all in something like O(n^1.999) or whatever.

well there are improved versions for example in $$$O(n^{\log_2(1+\sqrt{5})}) \approx O(n^{1.695})$$$ from Chazelle or in $$$O(n^{1.5} \log{n})$$$ from Mairson and Stolfi. Thats still slower than $$$O(n \log{n})$$$ but i don't know any better algorithms for this or any lower bounds for the counting problem...