[POJ 1263] | Eurce's Blog

计算几何

题意：给出二维平面上一个起始点和光线方向，以及平面上最多25个反射球面，问光线每次反射时击中的球编号。当不再击中球面或是反射了超过10次后终止计算。题目保证起始点不在球内，且不会沿切线方向击中球。

分析：由于数据量不大，可以每次计算出光线方向上与每个球的交点，按距离排序后取最近的一个点，根据入射角和切点算出反射角。迭代以上过程10次即可。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define eps 1e-8

int t,n,pl;
double x,y,xd,yd,a,b,c;

struct S
{
    double x,y,r;
}s[25];

struct P
{
    int si;
    double d,x,y;
    bool operator < (const P& p) const
    {
        return d<p.d;
    }
}p[50];

void init()
{
    int i,j,k,l;
    for(i=0;i<n;i++)
        scanf("%lf%lf%lf",&s[i].x,&s[i].y,&s[i].r);
    scanf("%lf%lf%lf%lf",&x,&y,&xd,&yd);
}

void addp(int si,double d,double x,double y)
{
    p[pl].si=si; p[pl].d=d; p[pl].x=x; p[pl].y=y; pl++;
}

void calcp(int si)
{
    double x0=s[si].x,y0=s[si].y,r=s[si].r,x1,y1,x2,y2,d;
    double a0,b0,c0;
    if(fabs(a)<eps)
    {
        y1=y2=-c;
        x1=x0+sqrt(r*r-pow(c+y0,2));
        x2=x0-sqrt(r*r-pow(c+y0,2));
    }
    else
    {
        a0=(b*b)/(a*a)+1;
        b0=2*(b*(c+a*x0)/(a*a)-y0);
        c0=pow(c+a*x0,2)/(a*a)+y0*y0-r*r;
        y1=(-b0+sqrt(b0*b0-4*a0*c0))/(2*a0);
        x1=-(b*y1+c)/a;
        y2=(-b0-sqrt(b0*b0-4*a0*c0))/(2*a0);
        x2=-(b*y2+c)/a;
    }
    if(fabs(xd)>eps)
    {
        if((x1-x)/xd>eps)
        {
            d=sqrt(pow(x1-x,2)+pow(y1-y,2));
            addp(si,d,x1,y1);
        }
        if((x2-x)/xd>eps)
        {
            d=sqrt(pow(x2-x,2)+pow(y2-y,2));
            addp(si,d,x2,y2);
        }
    }
    else
    {
        if((y1-y)/yd>eps)
        {
            d=sqrt(pow(x1-x,2)+pow(y1-y,2));
            addp(si,d,x1,y1);
        }
        if((y2-y)/yd>eps)
        {
            d=sqrt(pow(x2-x,2)+pow(y2-y,2));
            addp(si,d,x2,y2);
        }
    }
}

void xng()
{
    double xs,ys,ad,as;
    xd=-xd;
    yd=-yd;
    ad=atan2(yd,xd);
    x=p[0].x;
    y=p[0].y;
    xs=x-s[p[0].si].x;
    ys=y-s[p[0].si].y;
    as=atan2(ys,xs);
    ad=as-(ad-as);
    xd=cos(ad);
    yd=sin(ad);
}

void solve()
{
    int i,j,k,l;
    printf("Scene %d\n",++t);
    for(l=0;l<11;l++)
    {
        if(l)
            printf(" ");
        if(fabs(yd)<eps)
        {
            a=0;
            b=1;
            c=-y;
        }
        else
        {
            a=1;
            b=-xd/yd;
            c=-x-b*y;
        }
        pl=0;
        for(i=0;i<n;i++)
        {
            if(fabs(a*s[i].x+b*s[i].y+c)/sqrt(a*a+b*b)<s[i].r-eps)
                calcp(i);
        }
        if(!pl)
        {
            puts("inf");
            break;
        }
        else if(l==10)
        {
            puts("...");
            break;
        }
        sort(p,p+pl);
        printf("%d",p[0].si+1);
        xng();
    }
    puts("");
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-8

int t,n,pl;

double x,y,xd,yd,a,b,c;

struct S

{

double x,y,r;

}s[25];

struct P

{

int si;

double d,x,y;

bool operator < (const P& p) const

{

return d<p.d;

}

}p[50];

void init()

{

int i,j,k,l;

for(i=0;i<n;i++)

scanf("%lf%lf%lf",&s[i].x,&s[i].y,&s[i].r);

scanf("%lf%lf%lf%lf",&x,&y,&xd,&yd);

}

void addp(int si,double d,double x,double y)

{

p[pl].si=si; p[pl].d=d; p[pl].x=x; p[pl].y=y; pl++;

}

void calcp(int si)

{

double x0=s[si].x,y0=s[si].y,r=s[si].r,x1,y1,x2,y2,d;

double a0,b0,c0;

if(fabs(a)<eps)

{

y1=y2=-c;

x1=x0+sqrt(r*r-pow(c+y0,2));

x2=x0-sqrt(r*r-pow(c+y0,2));

}

else

{

a0=(b*b)/(a*a)+1;

b0=2*(b*(c+a*x0)/(a*a)-y0);

c0=pow(c+a*x0,2)/(a*a)+y0*y0-r*r;

y1=(-b0+sqrt(b0*b0-4*a0*c0))/(2*a0);

x1=-(b*y1+c)/a;

y2=(-b0-sqrt(b0*b0-4*a0*c0))/(2*a0);

x2=-(b*y2+c)/a;

}

if(fabs(xd)>eps)

{

if((x1-x)/xd>eps)

{

d=sqrt(pow(x1-x,2)+pow(y1-y,2));

addp(si,d,x1,y1);

}

if((x2-x)/xd>eps)

{

d=sqrt(pow(x2-x,2)+pow(y2-y,2));

addp(si,d,x2,y2);

}

else

{

if((y1-y)/yd>eps)

{

d=sqrt(pow(x1-x,2)+pow(y1-y,2));

addp(si,d,x1,y1);

}

if((y2-y)/yd>eps)

{

d=sqrt(pow(x2-x,2)+pow(y2-y,2));

addp(si,d,x2,y2);

}

void xng()

{

double xs,ys,ad,as;

xd=-xd;

yd=-yd;

ad=atan2(yd,xd);

x=p[0].x;

y=p[0].y;

xs=x-s[p[0].si].x;

ys=y-s[p[0].si].y;

as=atan2(ys,xs);

ad=as-(ad-as);

xd=cos(ad);

yd=sin(ad);

}

void solve()

{

int i,j,k,l;

printf("Scene %d\n",++t);

for(l=0;l<11;l++)

{

if(l)

printf(" ");

if(fabs(yd)<eps)

{

a=0;

b=1;

c=-y;

}

else

{

a=1;

b=-xd/yd;

c=-x-b*y;

}

pl=0;

for(i=0;i<n;i++)

{

if(fabs(a*s[i].x+b*s[i].y+c)/sqrt(a*a+b*b)<s[i].r-eps)

calcp(i);

}

if(!pl)

{

puts("inf");

break;

}

else if(l==10)

{

puts("...");

break;

}

sort(p,p+pl);

printf("%d",p[0].si+1);

xng();

}

puts("");

}

int main()

{

while(~scanf("%d",&n)&&n)

{

init();

solve();

}

return 0;

}

ps：分类表最后一题了。还差得远，继续努力。