1940 Polygon Programming with Ease
問題概要
多角形の各辺の中点を順に結んだ多角形が与えられる。
元の多角形を求めよ。
解法
求める多角形の頂点をx1,x2…,xnとし、与えられる多角形の頂点をb1,b2,…,bnとすれば、
b1=(x1+x2)/2, b2=(x2+x3)/2, ……
という関係が成り立つことがわかる。
したがってこれらはn元連立一次方程式を作っているので、連立方程式を解けば答えが求まる。
ソースコード
spaghetti sourceの行列・LU分解のコードを使用。
int main(){ int n; while(~scanf("%d",&n)){ matrix A(n,array(n,0)); array b,c; rep(i,n){ double e,f; scanf("%lf%lf",&e,&f); b.pb(e); c.pb(f); } rep(i,n)A[i][i]=A[i][(i+1)%n]=0.5; LUinfo data=LU_decomposition(A); b=LU_backsubstitution(data,b); c=LU_backsubstitution(data,c); printf("%d ",n); rep(i,n)printf("%.6f %.6f%c",b[i],c[i],i==n-1?'\n':' '); } return 0; }