「清北国庆模拟D1T2」线段 - 计算几何

题目大意

---

题目分析

毒瘤计算几何特判题。

首先如果两个点之间直接连通，之间不跨越墙和镜子（与镜子重叠不算跨越）那么直接输出YES。

否则只可能通过镜子反射。
那么从点$A$作镜子的对称点$A’$，将$A’$与$B$连边，若连线与镜子没有交点，说明不可能通过镜子反射看到对方，输出NO。

计算出连线与镜子的交点$P$，若$A\rightarrow P\rightarrow B$不与墙相交，就输出YES，否则输出NO。

计算对称点可以用一般式的公式计算，也可以旋转向量重置长度。
我选择的是前者。

另外毒瘤刘汝佳的求直线交点有误。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const double eps=1e-8;
int dcmp(double x) {
	if(fabs(x)<eps)return 0;
	else if(x<0)return -1;
	else return 1;
}
struct Point {
	double x,y;
	Point() {}
	Point(double _x,double _y):x(_x),y(_y) {}
	Point operator + (const Point& a) const {
		return Point(x+a.x,y+a.y);
	}
	Point operator - (const Point& a) const {
		return Point(a.x-x,a.y-y);
	}
	Point operator * (const double a) const {
		return Point(x*a,y*a);
	}
	bool operator == (Point b) {
		if(dcmp(x-b.x)==0&&dcmp(y-b.y)==0)return true;
		else return false;
	}
} ;
typedef Point Vector; //向量与点定义为同样的结构体，但应在概念上区分 
double Dot(Vector a,Vector b) { //点积
	return a.x*b.x+a.y+b.y;
}
double Cross(Vector a,Vector b) { //叉积
	return a.x*b.y-b.x*a.y;
}
bool OnSegment(Point Start,Point End,Point p) { //判断点p是否在线段上
	return dcmp(Cross(Start-p,End-p))==0&&dcmp(Dot(Start-p,End-p))<0;
}
bool Segment_Intersection(Point a1,Point a2,Point b1,Point b2) { //判断两线段是否相交 
	double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
	if(OnSegment(a1,a2,b1)||OnSegment(a1,a2,b2)||OnSegment(b1,b2,a1)||OnSegment(b1,b2,a2))return true;
	return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
bool OnSegment(Point a1,Point a2,Point b1,Point b2) { //判断两线段是否重叠 
	double c1=Cross(b1-a1,b2-a1),c2=Cross(b1-a2,b2-a2);
	return dcmp(c1)==0&&dcmp(c2)==0;
}
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w) { //求P+tv与Q+tw交点（需保证有相交） 参数方程版 
	Vector u=P-Q;
	double t=Cross(u,w)/Cross(v,w);
	return P+v*t;
}
Point HJA,YJQ,W1,W2,M1,M2;
struct Line {
	double a,b,c;
};
Line Get_Line(Point p1,Point p2) {
	Line l;
	l.a=p2.y-p1.y;
	l.b=p1.x-p2.x;
	l.c=p2.x*p1.y-p1.x*p2.y;
	return l;
}
Point Get_Symmetry(Point p,Point a,Point b) {
	Line l=Get_Line(a,b);
	Point p2;
	double d=l.a*l.a+l.b*l.b;
	p2.x=(l.b*l.b*p.x-l.a*l.a*p.x-2*l.a*l.b*p.y-2*l.a*l.c)/d;
	p2.y=(l.a*l.a*p.y-l.b*l.b*p.y-2*l.a*l.b*p.x-2*l.b*l.c)/d;
	return p2;
}
bool Check() {
	if(!Segment_Intersection(HJA,YJQ,W1,W2)) //没有被墙阻挡 
		if(!Segment_Intersection(HJA,YJQ,M1,M2)||OnSegment(HJA,YJQ,M1,M2))return true; //没有被镜子阻挡
	Point HJA1=Get_Symmetry(HJA,M1,M2);
	if(!Segment_Intersection(HJA1,YJQ,M1,M2)||OnSegment(HJA1,YJQ,M1,M2)||HJA1==YJQ)return false; //对称连线不与镜子相交
	Point a=GetLineIntersection(HJA1,HJA1-YJQ,M1,M1-M2); //交点 
	if(Segment_Intersection(HJA,a,W1,W2)||Segment_Intersection(a,YJQ,W1,W2))return false;
	return true;
}
int main() {
	cin>>HJA.x>>HJA.y>>YJQ.x>>YJQ.y>>W1.x>>W1.y>>W2.x>>W2.y>>M1.x>>M1.y>>M2.x>>M2.y;
	puts(Check()?"YES":"NO");
	Point p=GetLineIntersection(Point(0,0),Point(1,1),Point(0,1),Point(1,-1));
	return 0;
}