題目鏈接：
http://acm.hnu.cn:8080/online/?action=problem&type=show&id=11195
#include <iostream>
#include <string.h>
#include <math.h>
#define eps 1e-3
using namespace std;
struct point
{
double x, y;
point(){}
void read(){
scanf("%lf,%lf", &x, &y);
}
void write(){
printf("%.0lf,%.0lf\n", x, y);
}
};
struct line
{
char flag;
point a, b;
line(){}
void read(){
getchar();
scanf("%c %lf,%lf %lf,%lf", &flag, &a.x, &a.y, &b.x, &b.y);
}
void write(){
printf("%c %.0lf,%.0lf %.0lf,%.0lf\n", flag, a.x, a.y, b.x, b.y);
}
};
//精度控制
int sig(double a)
{return (a > eps) - (a < -eps);}
//判兩直線平行
int parallel(point u1,point u2,point v1,point v2){
return sig((u1.x-u2.x)*(v1.y-v2.y)-(v1.x-v2.x)*(u1.y-u2.y));
}
//計算cross product (P1-P0)x(P2-P0)
double xmult(point p1,point p2,point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
// (op-sp)·(op-ep)點積
double dotmul(point sp, point ep, point op){
return (op.x-sp.x) * (op.x-ep.x) + (op.y-sp.y) * (op.y-ep.y);
}
//判兩點在線段異側,點在線段上返回0
int opposite_side(point p1,point p2,point l1,point l2){
return xmult(l1,p1,l2)*xmult(l1,p2,l2)<-eps;
}
//判兩線段相交,不包括端點和部分重合
int intersect_ex(point u1,point u2,point v1,point v2){
//if(!parallel(u1,u2,v1,v2))
return opposite_side(u1,u2,v1,v2)&&opposite_side(v1,v2,u1,u2);
//else return 0;
}
//計算兩直線交點,注意事先判斷直線是否平行!
point intersection(point u1,point u2,point v1,point v2){
point ret=u1;
double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
ret.x+=(u2.x-u1.x)*t;
ret.y+=(u2.y-u1.y)*t;
return ret;
}
//一個double的平方
double sqr(double a)
{return a*a;}
//返回p向量的模的平方
double mo(point p)
{return p.x*p.x + p.y*p.y;}
//兩點距離
double dist(point a, point b)
{return sqrt( sqr(a.x - b.x) + sqr(a.y - b.y) );}
// 返回點p以點o為圓心逆時針旋轉alpha(單位：弧度)后所在的位置
point rotate(point o, double alpha, point p)
{
point tp;
p.x -= o.x; p.y -= o.y;
tp.x=p.x*cos(alpha) - p.y*sin(alpha)+o.x;
tp.y=p.y*cos(alpha) + p.x*sin(alpha)+o.y;
return tp;
}
// 返回頂角在o點，起始邊為os，終止邊為oe的夾角(單位：弧度)
double angle(point o, point s, point e)
{
point os, oe;
os.x = s.x - o.x; os.y = s.y - o.y;
oe.x = e.x - o.x; oe.y = e.y - o.y;
double cosfi, norm, fi;
cosfi = dotmul(s, e, o);
norm = sqrt(mo(os) * mo(oe));
cosfi /= norm;
if(sig(cosfi - 1.0) >= 0 ) return 0;
if(sig(cosfi + 1.0) <= 0 ) return M_PI;
fi = acos(cosfi);
//o.write(); s.write(); e.write();
return fi;
}
//返回op向量與線段s反射的向量（p在s上）
point reflct(point o, point p, line s)
{
point new_dic;
double ang = angle(p, o, s.a);
if( sig(ang - M_PI/2) > 0) ang = M_PI - ang;
ang = M_PI - 2 * ang;
new_dic = rotate(p, ang, o);
if(angle(p, o, s.a) != angle(p, new_dic, s.b) ) new_dic = rotate(p, 2*M_PI-ang, o);
new_dic.x -= p.x;
new_dic.y -= p.y;
return new_dic;
}
line l[101];
int n, answer[101];
struct nod
{
point ini, dic;
}q[101];
void work(point a, point b)
{
int cnt = 0, close = -1, open = 0;
point exp, new_ini, ini = a, dic = b, cro, new_dic;
double mindis;
int minnum;
memset(answer, 0, sizeof(answer));
q[0].ini = ini;
q[0].dic = dic;
while(close < open)
{
close ++;
ini = q[close].ini;
dic = q[close].dic;
exp.x = ini.x + 5000 * dic.x;
exp.y = ini.y + 5000 * dic.y;
//把射線變成線段
int i;
mindis = 999999999.0; minnum = -1;
for(i = 0; i < n; i ++)
{
if( intersect_ex(ini, exp, l[i].a, l[i].b) )//兩線段相交
{
new_ini = intersection(ini, exp, l[i].a, l[i].b);
if( mindis > dist( ini, new_ini) )
{
minnum = i;
mindis = dist(ini, new_ini);
}
}
}
new_ini = intersection(ini, exp, l[minnum].a, l[minnum].b);
if(minnum == -1) continue;
if(l[minnum].flag == 'D')
{
answer[minnum] = 1;
continue;
}
if(l[minnum].flag == 'S')
{
open ++;
q[open].ini = new_ini;
q[open].dic = dic;
}
open ++;
new_dic = reflct(ini, new_ini, l[minnum]);
q[open].ini = new_ini;
q[open].dic = new_dic;
}
}
void out()
{
int flag = 0;
for(int i = 0; i < n; i ++) if(answer[i])
{
flag = 1;
printf("%d\n",i + 1);
}
if(!flag) puts("NO BEAMS DETECTED");
}
int main()
{
int test, x = 0;
point ini, dic;
scanf("%d", &test);
while(test -- )
{
printf("DATA SET #%d\n",++x);
ini.read(); dic.read();
scanf("%d", &n);
for(int i = 0; i < n; i ++)
{
l[i].read();
}
work(ini, dic);
out();
}
}