求助

学术版

Spasmodic @ 2021-01-17 16:31:12

有 n 条线 两两有交点

已知 m 组三线共点关系 求交点个数最多有几个

样例：

6 5
1 2 3
1 2 4
1 2 5
3 4 6

输出

1

by Spasmodic @ 2021-01-17 16:47:17

@我知道了王子 qwq？那我怎么知道有几个这样的点

by Spasmodic @ 2021-01-17 16:49:20

@我知道了王子 但是给出的交点可能重合

by AsunderSquall @ 2021-01-17 16:50:34

等一下，我再冷静一下

by AsunderSquall @ 2021-01-17 16:52:23

我 naive 了

by Unordered_AFOer @ 2021-01-17 17:59:41

@happyChristmas 数据范围多少

by Spasmodic @ 2021-01-17 18:10:52

@HpyX 反正有低于 O(m^2) 做法就说一下

by Unordered_AFOer @ 2021-01-17 18:21:05

@happyChristmas az,那我爬了

by Spasmodic @ 2021-01-17 18:25:22

好像是 $O(m(m+n))$ 的……不管
|