Official

E - 凸図形の合成 / Composition of Convex Shapes Editorial by physics0523


まず、以下の考察をします。

  • 点同士のミンコフスキー和は点である。
  • 点と線分 \(l\) とのミンコフスキー和は \(l\) に平行な線分である。
  • 凸多角形と他の図形とのミンコフスキー和は凸多角形である。
  • 線分 \(l\) と線分 \(m\) のミンコフスキー和は以下の場合分けで求まる。
    • \(l\) と \(m\) とが平行であるとき、ミンコフスキー和は \(l,m\) に平行な線分である。
    • \(l\) と \(m\) とが平行でないとき、ミンコフスキー和は(正の面積を持つ)凸多角形となる。

ミンコフスキー和が凸多角形にならない場合を数え、全体から引くことを考えます。

先程の考察を整理すると、数えるべき場合は以下の \(2\) 通りであることが分かります。

  • \(S\) に点しか含まれない場合。
  • \(S\) に \(1\) つ以上の線分と \(0\) 個以上の点が含まれ、含まれる線分が全て平行である。

前者は点の数を \(p\) として \(2^p-1\) と求められます。
後者は、図形が直線かどうかを (ベクトルの外積などを用いて)判定して平行な線同士がグループとなるように分類した上で、各グループの大きさを \(g\) とするとそのグループは答えに \((2^g-1)2^p\) だけ寄与することが分かります。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using pl=pair<ll,ll>;

const ll mod=1000000007;

ll power(ll a,ll b){
  ll x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}

bool isline(pl a,pl b,pl c){
  b.first-=a.first;
  b.second-=a.second;
  c.first-=a.first;
  c.second-=a.second;
  return ((b.first*c.second-b.second*c.first)==0);
}

int main(){
  ll N;
  cin >> N;
  ll point=0;
  map<pl,ll> mp;
  for(ll i=0;i<N;i++){
    ll K;
    cin >> K;
    vector<pl> p(K);
    for(auto &nx : p){
      cin >> nx.first >> nx.second;
    }
    if(K==1){point++; continue;}
    sort(p.begin(),p.end());
    bool line=true;
    for(ll i=2;i<K;i++){
      if(!isline(p[0],p[1],p[i])){line=false;}
    }
    if(line){
      pl vec={p[1].first-p[0].first,p[1].second-p[0].second};
      ll g=gcd(vec.first,vec.second);
      vec.first/=g;
      vec.second/=g;
      mp[vec]++;
    }
  }

  ll res=(mod+power(2,N)-1)%mod;
  
  // single point
  res+=(mod+1-power(2,point)); res%=mod;

  for(auto &nx : mp){
    // line
    ll del=(mod+power(2,nx.second)-1)%mod;
    del*=power(2,point); del%=mod;
    res+=(mod-del); res%=mod;
  }

  cout << res << "\n";
  return 0;
}