ICPC用幾何ライブラリの実装方針を固める作業中…
問題概要
2本の直線で囲まれた、幅 $W$ の風の通り道に、$N$ 個の多角形が与えられる。
2つの障害物の間には、障害物間の最小距離に比例した風の流れが存在する。距離1あたりに、流量1流れるとした時、この通り道における風の流量を求めよ。
制約
$1 \leq W \leq 10^{4}$
$0 \leq N \leq 200$
1つの多角形の頂点数は、$40$ 以下
$0 < x < W, 0 < y < 10^{4}$
解法
両脇の壁も多角形として捉えることにします。
それぞれの多角形のペアに対して、最短距離を重みとする辺を張ったグラフを考えた時、両端の壁の間の最短距離が風の流量と一致します。
(それぞれの壁をsource, sinkとして、同様のグラフにおける最小カットと流量が一致すると問題を定式化した時に、適切に流量に関係する辺を抜き出すとDAGになっていて、だから最小カットが最短経路問題として解くことが出来る、という認識をしています。)
後は多角形間の距離さえ求めれば、ダイクストラなどの最短経路問題に帰着されます。距離を求める際、2つの多角形以外を無視した値を求めていますが、最短経路を求める上では影響を及ぼさないので、雑に求めて大丈夫ということになります。
実装
#pragma GCC optimize ("Ofast") #include <bits/stdc++.h> using namespace std; typedef long long int ll; struct point{ double x,y; point() {} point(double x,double y) : x(x), y(y) {} point operator- (const point& p){ return point(x-p.x, y-p.y); } double dist(point p){ return sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y)); } }; double dot(point a, point b){ return a.x*b.x + a.y*b.y; } double cross(point a, point b){ return a.x*b.y - a.y*b.x; } struct line{ point A,B; line(point A,point B) : A(A), B(B) {} double len(){ return A.dist(B); } // 直線と点の距離 double l_dist(point p){ double crs = cross(p-A, B-A); return abs(crs) / len(); } // 線分と点の距離 double s_dist(point p){ if(dot(p-A, B-A) < 0) return A.dist(p); else if(dot(p-B, A-B) < 0) return B.dist(p); else return l_dist(p); } }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int w,n; while(cin >> w >> n,w){ vector<vector<point>> v(n+2); for (int i = 0; i < n; ++i) { int m; cin >> m; for (int j = 0; j < m; ++j) { int x,y; cin >> x >> y; v[i].push_back(point(x,y)); } v[i].push_back(v[i][0]); } v[n].push_back(point(0,0)); v[n].push_back(point(0,20000)); v[n+1].push_back(point(w,0)); v[n+1].push_back(point(w,20000)); const double inf = 1e9; vector<vector<double>> d(n+2,vector<double>(n+2, inf)); // 多角形iとjの距離 auto dis = [&](int i,int j)->double{ if(i == j) return 0; double res = inf; for(auto p:v[i]){ for (int k = 0; k+1 < v[j].size(); ++k) { line l = line(v[j][k], v[j][k+1]); res = min(res, l.s_dist(p)); } } swap(i, j); for(auto p:v[i]){ for (int k = 0; k+1 < v[j].size(); ++k) { line l = line(v[j][k], v[j][k+1]); res = min(res, l.s_dist(p)); } } return res; }; for (int i = 0; i < n+2; ++i) { for (int j = i; j < n+2; ++j) { auto r = dis(i, j); d[i][j] = d[j][i] = r; } } for (int k = 0; k < n+2; ++k) { for (int i = 0; i < n+2; ++i) { for (int j = 0; j < n+2; ++j) { d[i][j] = min(d[i][j], d[i][k]+d[k][j]); } } } printf("%.9f\n", d[n][n+1]); } }
