Official
E - 凸図形の合成 / Composition of Convex Shapes Editorial
by
E - 凸図形の合成 / Composition of Convex Shapes Editorial
by
physics0523
Editorial for printing
まず、以下の考察をします。
- 点同士のミンコフスキー和は点である。
- 点と線分 \(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;
}
posted:
last update:
