当前位置: 代码迷 >> Ruby/Rails >> HDU 2857 Mirror and Light (计算几何求 对称点跟两直线的交点)
  详细解决方案

HDU 2857 Mirror and Light (计算几何求 对称点跟两直线的交点)

热度:678   发布时间:2016-04-29 02:26:13.0
HDU 2857 Mirror and Light (计算几何求 对称点和两直线的交点)


题意:给你镜子的位置(用两点确定的一条直线表示),光源,光的反射点,求光在镜子的折射点


计算几何的模板,注意斜率!!!


模板1:


#include<cstdio>#include<stdlib.h>#include<string.h>#include<string>#include<map>#include<cmath>#include<iostream>#include <queue>#include <stack>#include<algorithm>#include<set>using namespace std;#define INF 1e8#define eps 1e-4#define ll __int64#define maxn 500010#define mol 1000000007struct point {	double x,y;};point symmetric_point(point p1, point l1, point l2)// 求p1的对称点{	point 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);		if(k + eps > 0 && k - eps < 0)//斜率为零		{			ret.x = p1.x;			ret.y = l1.y - (p1.y - l1.y);		}		else		{			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;}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;}int main(){	int t;	scanf("%d",&t);	while(t--)	{		point m1,m2,l1,l2;		scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&m1.x,&m1.y,&m2.x,&m2.y,&l1.x,&l1.y,&l2.x,&l2.y);		point tmp=symmetric_point(l1,m1,m2);		point ans=intersection(tmp,l2,m1,m2);		printf("%.3lf %.3lf\n",ans.x,ans.y);	}	return 0;}


模板2(利用点到直线上的最近点避免斜率):

#include<cstdio>#include<cmath>using namespace std;const double eps=1e-8;struct point{    double x,y;};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;}point ptoline(point p,point l1,point l2){    point t=p;    t.x+=l1.y-l2.y,t.y+=l2.x-l1.x;    return intersection(p,t,l1,l2);}point m1,m2,l1,l2;int main(){    int n;    scanf("%d",&n);    while(n--){        scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&m1.x,&m1.y,&m2.x,&m2.y,&l1.x,&l1.y,&l2.x,&l2.y);        point dot = ptoline(l1,m1,m2);        point now;        now.x = 2*dot.x - l1.x;//源点与对称点的中点落在直线上        now.y = 2*dot.y - l1.y;        point ans = intersection(now,l2,m1,m2);        printf("%.3lf %.3lf\n",ans.x,ans.y);    }    return 0;}



  相关解决方案