上半分の点の集合が変わるのはO(N^2)回ある。2点を通る直線とy軸の交点を列挙すればこの区間を左側で分けられる。 左側がy=tのときの右側が取れる範囲の大きさは1次式で、上半分の点の集合が同じなら同じ式となるはず。 ということは、この領域の中央に代表…