ABC131 F. Must Be Rectangular!
問題
2次元座標にN個の点が与えられる。
このとき、「座標(a,b),(a,d),(c,b),(c,d)のうちちょうど3箇所に点が存在するようなa,b,c,d(a!=c, b!=d)を選んで、残りの1箇所に点を追加する」という操作を繰り返す。
この操作回数の最大値を求めよ。
制約
- 1 <= N <= 10^5
- 1 <= x_i, y_i <= 10^5
- 与えられる各点に同じ位置のものはない
- 入力はすべて整数
解法
まず、答えとなる最終的な形を考える。
1回でも操作が行えるような頂点が存在する場合、そこに頂点を追加することで、長方形ができ、追加された頂点によってまた操作ができるようになって、これを繰り返すことで、巨大な格子が作れることがわかる。
したがって、この格子の形が求められれば、その格子の頂点からすでに存在する頂点を引けば操作回数の最大値がわかる。
格子を形成できる頂点は、同じx座標、または、y座標を共有しているはずなので、ある頂点から同じx座標、または、y座標になっている頂点を辿れる頂点すべてを見つければよく、これは、dfsで探すか、x座標とy座標それぞれを頂点とみなしてUnionFindで連結成分を見つけるようにすれば求められる。
あとは、各頂点のグループに対して、最大の操作回数を求めて合計すれば良い。
