首页 > 代码库 > Codeforces 32E Hide-and-Seek 求2点关于镜面反射 计算几何
Codeforces 32E Hide-and-Seek 求2点关于镜面反射 计算几何
题目链接:点击打开链接
需要注意的是镜子在与2个人共线时是不作为障碍物,但其他情况与墙一致
#include<cstdio> #include<iostream> #include<algorithm> #include<string.h> #include<math.h> using namespace std; #define point Point const double eps = 1e-8; const double PI = acos(-1.0); double ABS(double x){return x>0?x:-x;} int sgn(double x){ if(fabs(x) < eps)return 0; if(x < 0)return -1; else return 1; } struct Point { double x,y; void put(){printf("(%.0lf,%.0lf)\n",x,y);} Point(){} Point(double _x,double _y){ x = _x;y = _y; } Point operator -(const Point &b)const{ return Point(x - b.x,y - b.y); } //叉积 double operator ^(const Point &b)const{ return x*b.y - y*b.x; } //点积 double operator *(const Point &b)const{ return x*b.x + y*b.y; } //绕原点旋转角度B(弧度值),后x,y的变化 void transXY(double B){ double tx = x,ty = y; x = tx*cos(B) - ty*sin(B); y = tx*sin(B) + ty*cos(B); } }; struct Line { Point s,e; void put(){s.put();e.put();} Line(){} Line(Point _s,Point _e) { s = _s;e = _e; } //两直线相交求交点 //第一个值为0表示直线重合,为1表示平行,为0表示相交,为2是相交 //只有第一个值为2时,交点才有意义 pair<int,Point> operator &(const Line &b)const{ Point res = s; if(sgn((s-e)^(b.s-b.e)) == 0) { if(sgn((s-b.e)^(b.s-b.e)) == 0) return make_pair(0,res);//重合 else return make_pair(1,res);//平行 } double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e)); res.x += (e.x-s.x)*t; res.y += (e.y-s.y)*t; return make_pair(2,res); } }; double dist(Point a,Point b){return sqrt((a-b)*(a-b));} //*判断线段相交 bool inter(Line l1,Line l2) { return max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) && max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) && max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) && max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) && sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e)) <= 0 && sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e)) <= 0; } point symmetric_point(point p1, point l1, point l2) { point ret; if(ABS(l1.x-l2.x)<eps){ ret.y = p1.y; ret.x = 2*l1.x - p1.x; return ret; } if(ABS(l1.y-l2.y)<eps) { ret.x = p1.x; ret.y = 2*l1.y - p1.y; return ret; } if (l1.x > l2.x - eps && l1.x < l2.x + eps) { ret.x = (2 * l1.x - p1.x); ret.y = p1.y; } else { double k = (l1.y - l2.y ) / (l1.x - l2.x); ret.x = (2*k*k*l1.x + 2*k*p1.y - 2*k*l1.y - k*k*p1.x + p1.x) / (1 + k*k); ret.y = p1.y - (ret.x - p1.x ) / k; } return ret; } bool gongxian(Point a, Point b, Point c){ return ABS((a.y-b.y)*(a.x-c.x) - (a.y-c.y)*(a.x-b.x))<eps; } Point a,b; Line peo, wal, mir; bool work(){ // peo.put(); wal.put(); if((gongxian(a,mir.s,mir.e)&&gongxian(b,mir.s,mir.e))) { // a.put(); b.put(); mir.put(); puts("共线了"); return !inter(wal,peo); } else if(inter(mir,peo))return false; if(!inter(wal, peo)) return true; // puts("GEGE"); if(inter(wal,mir))return false; Point c = symmetric_point(b,mir.s,mir.e); Point d = symmetric_point(a,mir.s,mir.e); // c.put(); d.put(); Line ac, bd; ac.s = a, ac.e = c; bd.s = b, bd.e = d; if(!inter(ac,mir))return false; if(!inter(bd,mir))return false; if(inter(ac,wal))return false; if(inter(bd,wal))return false; return true; } int main(){ while(~scanf("%lf %lf",&a.x,&a.y)){ scanf("%lf %lf",&b.x,&b.y); scanf("%lf %lf %lf %lf", &wal.s.x, &wal.s.y, &wal.e.x, &wal.e.y); scanf("%lf %lf %lf %lf", &mir.s.x, &mir.s.y, &mir.e.x, &mir.e.y); peo.s = a, peo.e = b; work()?puts("YES"):puts("NO"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。