POJ 2194 Stacking Cylinders(两圆相切求圆心坐标)

POJ 2194 Stacking Cylinders(两圆相切求圆心坐标)

http://poj.org/problem?id=2194

题意: POJ2850 ZOJ2403

有多个圆堆叠在一起,它们被成了好多层.其中最下面那层有n个圆,从下往上每层圆依次减少1个.且上层的圆一定是与下层两个相邻的圆相切的.给定你最下层n个圆的圆心坐标,要你输出最上一层的圆心坐标.

分析:

大体思路是通过最下层的圆心坐标来依次递推出上一层圆心的坐标即可. 由于每个上层圆一定是由下层两个相邻的圆相切堆叠起来的,所以有下图:

总的来说,我们只需要能根据下面的两个圆心坐标和圆半径算出上面的那个圆心坐标即可最终推出最上点坐标.

AC代码:

//用C++提交,G++提交有打印double的BUG
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-10;
const int maxn=10+5;
struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;

Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x,A.y-B.y);
}

Vector operator+(Vector A,Vector B)
{
    return Vector(A.x+B.x,A.y+B.y);
}

Vector operator*(Vector A,double p)
{
    return Vector(A.x*p, A.y*p);
}

double Dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}

double Length(Vector A)
{
    return sqrt(Dot(A,A));
}

double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}

//向量A逆时针旋转特定角度,该角度对应的正弦和余弦值
Vector Rotate(Vector A,double sinv,double cosv)
{
    return Vector(A.x*cosv-A.y*sinv, A.x*sinv+A.y*cosv);
}

Point GetLineIntersection(Point P,Vector v,Point Q,Vector w)
{
    Vector u=P-Q;
    double t=Cross(w,u)/Cross(v,w);
    return P+v*t;
}
/***以上为刘汝佳模板***/

//根据底部的两圆心A和B来计算上层圆心,假设所求圆心为P点
Point get_upper_point(Point A,Point B)
{
    double len_AB=Length(A-B);
    double cosv= (len_AB/2)/2.0;
    double sinv=sqrt(1-cosv*cosv);
    Vector PA=Rotate(B-A,sinv,cosv);//旋转后的向量
    Vector PB=Rotate(A-B,-sinv,cosv);//旋转后的向量
    return GetLineIntersection(A,PA,B,PB);
}

int main()
{
    int n;
    double x[maxn];
    Point P[maxn][maxn];
    while(scanf("%d",&n)==1 && n)
    {
        for(int i=0;i<n;++i) scanf("%lf",&x[i]);
        sort(x,x+n);
        for(int i=0;i<n;++i)
            P[0][i]=Point(x[i],1.0);

        for(int i=1;i<n;++i)//从第1层开始递推该层所有圆心坐标
        {
            for(int j=0;j<n-i;++j)
                P[i][j]=get_upper_point(P[i-1][j],P[i-1][j+1]);
        }
        printf("%.4lf %.4lf\n",P[n-1][0].x,P[n-1][0].y);
    }
    return 0;
}