首页 > ACM题库 > HDU-杭电 > HDU 2857-Mirror and Light -计算几何-[解题报告]HOJ
2014
02-17

HDU 2857-Mirror and Light -计算几何-[解题报告]HOJ

Mirror and Light

问题描述 :

The light travels in a straight line and always goes in the minimal path between two points, are the basic laws of optics.

Now, our problem is that, if a branch of light goes into a large and infinite mirror, of course,it will reflect, and leave away the mirror in another direction. Giving you the position of mirror and the two points the light goes in before and after the reflection, calculate the reflection point of the light on the mirror.
  
You can assume the mirror is a straight line and the given two points can’t be on the different sizes of the mirror.

输入:

The first line is the number of test case t(t<=100).
  
The following every four lines are as follow:
  X1 Y1
  X2 Y2
  Xs Ys
  Xe Ye

  (X1,Y1),(X2,Y2) mean the different points on the mirror, and (Xs,Ys) means the point the light travel in before the reflection, and (Xe,Ye) is the point the light go after the reflection.

  The eight real number all are rounded to three digits after the decimal point, and the absolute values are no larger than 10000.0.

输出:

The first line is the number of test case t(t<=100).
  
The following every four lines are as follow:
  X1 Y1
  X2 Y2
  Xs Ys
  Xe Ye

  (X1,Y1),(X2,Y2) mean the different points on the mirror, and (Xs,Ys) means the point the light travel in before the reflection, and (Xe,Ye) is the point the light go after the reflection.

  The eight real number all are rounded to three digits after the decimal point, and the absolute values are no larger than 10000.0.

样例输入:

1
0.000 0.000
4.000 0.000
1.000 1.000
3.000 1.000

样例输出:

2.000 0.000 

#include <iostream>
 #include <iomanip>
 #include <cmath>
 using namespace std;
 struct Point {double x,y;}; //点
 struct Ldir{double dx,dy;}; //方向向量
 struct Lline{Point p; Ldir dir;}; //直线
 // 计算直线的一般式 Ax+By+C=0
 void format(Lline ln,double& A,double& B,double& C)
 {
     A=ln.dir.dy;
     B=-ln.dir.dx;
     C=ln.p.y*ln.dir.dx-ln.p.x*ln.dir.dy;
 }
 // 求点p1关于直线ln的对称点p2
 Point mirror(Point P,Lline ln)
 {
     Point Q;
     double A,B,C;
     format(ln,A,B,C);
     Q.x=((B*B-A*A)*P.x-2*A*B*P.y-2*A*C)/(A*A+B*B);
     Q.y=((A*A-B*B)*P.y-2*A*B*P.x-2*B*C)/(A*A+B*B);
     return Q;
 }
 //求线段交点 
 struct TLine
 {
     //直线标准式中的系数 
     double a, b, c;
 };
 TLine lineFromSegment(Point p1, Point p2) 
 { 
     TLine tmp; 
     tmp.a = p2.y - p1.y; 
     tmp.b = p1.x - p2.x; 
     tmp.c = p2.x * p1.y - p1.x * p2.y; 
     return tmp; 
 }
 /*求直线的交点,注意平形的情况无解,避免RE*/
 const double eps = 1e-6;    //注意一定要加,否则错误 
 Point LineInter(TLine l1, TLine l2)
 {
     //求两直线得交点坐标
     Point tmp; 
     double a1 = l1.a;
     double b1 = l1.b;
     double c1 = l1.c;
     double a2 = l2.a;
     double b2 = l2.b;
     double c2 = l2.c;
     //注意这里b1 = 0 
     if(fabs(b1) < eps){
         tmp.x = -c1 / a1; 
         tmp.y = (-c2 - a2 * tmp.x) / b2;
     }       
     else{
         tmp.x = (c1 * b2 - b1 * c2) / (b1 * a2 - b2 * a1);
         tmp.y = (-c1 - a1 * tmp.x) / b1;
     }
     return tmp;
 }
 int main()
 {
     int T;
     cin>>T;
     cout<<setiosflags(ios::fixed)<<setprecision(3);
     while(T--){
         Point p1,p2,ps,pe;
         Lline l;
         cin>>p1.x>>p1.y;
         cin>>p2.x>>p2.y;
         cin>>ps.x>>ps.y;
         cin>>pe.x>>pe.y;
         l.p = p1;
         l.dir.dx = p2.x - p1.x;
         l.dir.dy = p2.y - p1.y;
         Point duichen = mirror(ps,l);    //求对称点
         //cout<<duichen.x<<' '<<duichen.y<<endl;
         TLine l1,l2;
         l1 = lineFromSegment(p1,p2);
         l2 = lineFromSegment(duichen,pe);
         Point inter =  LineInter(l1,l2);    //求交点 
         cout<<inter.x<<' '<<inter.y<<endl;
     }
     return 0;
 }

解题参考:http://www.cnblogs.com/yym2013/p/3543190.html


  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }