ARC082 E : ConvexScore(700)
作成日：2017.09.03
最終更新日：2017.09.03
問題概要
二次元平面上にある$N$個の点$(X_i , y_i)$が与えられる。
$N$個の点の部分集合$S$で$S$に含まれる点を頂点とする凸多角形が存在するものを考える。
各$S$に対してそのスコアを$N$個の点で$S$の凸包の内部と境界(頂点を含む)にある点の個数を$n$とした時$2^{n-|S|}$とする。
条件を満たすすべての$S$のスコアの総和を$998244353$で割った余りを求めよ。
制約
$1 \leq N \leq 200$
$0 \leq x_i , y_i < 10^4$
$i \neq j$ならば$(x_i , y_i) \neq (x_j , y_j)$
$x_i , y_i$は整数
考え方
凸多角形を作るためには点は3つ以上必要であるから、3点以上選ぶことのみを考える。
選んだ点の集合$S$を頂点とする凸多角形が存在する時、明らかにその多角形は$S$の凸包と一致する(*)。
その凸包の内部と境界にある$S$に含まれない点をいくつか$S$に加えた点の集合$T$を考えると、$T$の凸包は$S$の凸包と一致する。
また、$T$は(*)の対偶から凸多角形をなさないことが分かる。
$T$は$2^{n-|S|} - 1$種類作れることから、$S$と合わせると凸包が$S$になる点の選び方は$2^{n-|S|}$個存在することが分かる。
これは$S$のスコアに等しい。
以上より点を3つ以上選んだ時に凸包が凸多角形になる選び方が答えであることが分かる。
これは選んだ点の集合で同一直線上にないものの数である。
同一直線上に点がいくつ存在するかは直線上のある点と他の点を結んだ時の傾きを見れば分かる。
mapを使って数えれば$O(N^2 log \: N)$で求められるので十分高速である。
ソースコード
マクロ等はこちら
const int MC = 210;
const LL mod = 998244353;
int N;
int x[MC] , y[MC];
LL sel[MC]; //sel[i] : i個の点から3個以上の点を選ぶ時の選び方の総数
LL l[MC]; //l[i] : i個の点が乗っている直線の数のi倍(重複して数えられるため)
int gcd(int a , int b){
return b ? gcd(b,a%b) : a;
}
int main(){
scanf("%d" , &N);
repp(i,0,N){
scanf("%d%d" , x + i , y + i);
}
sel[3] = 8;
repp(i,4,MC){
sel[i] = sel[i-1] * 2 % mod;
(sel[i-1] += mod - i - (i-1) * (i-2) / 2) %= mod;
}
repp(i,0,N){
map<P2,int> M;
repp(j,0,N){
if(i==j) continue;
int dx = x[j] - x[i];
int dy = y[j] - y[i];
if(dx < 0){
dx *= -1;
dy *= -1;
}
if(dx == 0) dy = 1;
else if(dy == 0) dx = 1;
else {
int g = gcd(dx,abs(dy));
dx /= g;
dy /= g;
}
++M[MP(dx,dy)];
}
for(auto z : M) ++l[z.second + 1];
}
LL ans = sel[N];
repp(i,3,N+1){
(ans += (mod - sel[i]) * (l[i]/i)) %= mod;
}
printf("%lld\n" , ans);
return 0;
}解法まとめ
各点において他の点と直線で結んだ時の傾きを求め、2つ以上同じ傾きのものがあればそれを数える。(22-42行)
$N$個の点から$3$個以上の点を選ぶ時の選び方から、同一直線状に乗っている$3$個以上の点の選び方を引いたものが答えである。(43-47行)