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;
}