首页 > ACM题库 > HDU-杭电 > HDU 3712-Detector Placement-计算几何-[解题报告]HOJ
2015
02-21

HDU 3712-Detector Placement-计算几何-[解题报告]HOJ

Detector Placement

问题描述 :

Dr. Gale is testing his laser system. He uses a detector to collect the signals from a fixed laser generator. He also puts a special prism in the system so that he can filter the noise. But he is not sure where to put the detector to collect the signals. Can you help him with this problem?

Binary Number

Here n1 and n2 are the refractive indices of the two media. In order to simplify the problem, here we assume the prism is a triangle. The laser generator will not be placed on the surface of the prism or inside the prism. The laser goes in one direction and the detector can receive signals from any direction. The detector is place on the ground where th y-coordinate is zero. There is no energy lost in the refraction. That is to say, there is no reflection in the signal transmission. You can assume that there is no total reflection or the situation that the laser passes the vertex of the prism. Given the position and the direction of the laser generator and the prism, you are asked to find the position of detector so that it can receive the signals from the laser generator.

输入:

The input contains multiple test cases. The first line is the total number of cases T (T ≤ 100). The first line of each test case contains 2 integers, indicating the x and y coordinates of the laser generator respectively.The second line contains 2 integers describing a point the laser will go through when the prism is not placed. The third line contains 6 integers describing the three vertices of the prism. The fourth line contains a real number u, the refractive index of the prism (1 < u ≤ 10). We assume the refractive index of the air is always 1.0. The absolute value of the coordinates will not exceed 1000. The y coordinates are all nonnegative. The prism and the laser generator are strictly above the ground.

输出:

The input contains multiple test cases. The first line is the total number of cases T (T ≤ 100). The first line of each test case contains 2 integers, indicating the x and y coordinates of the laser generator respectively.The second line contains 2 integers describing a point the laser will go through when the prism is not placed. The third line contains 6 integers describing the three vertices of the prism. The fourth line contains a real number u, the refractive index of the prism (1 < u ≤ 10). We assume the refractive index of the air is always 1.0. The absolute value of the coordinates will not exceed 1000. The y coordinates are all nonnegative. The prism and the laser generator are strictly above the ground.

样例输入:

2
0 10
0 0
-1 3 1 2 -1 1
1.325
0 10
0 20
-1 3 1 2 -1 1
1.325

样例输出:

-0.658
Error

题意:给一束激光,一个三棱柱,三棱柱会折射光,问这束激光最终是否会和y = 0相交;

分析:模拟题,为了方便处理折射角,事先求出每条边的向内和向外的法向量;

findpoint : 找第一交点

step1:  判断激光是否和三角形有规范相交;

step2: 第一次折射;

step3:第二次折射,可能无法折射;

 #include<cstdio>
 #include<cstring>
 #include<cstdlib>
 #include<iostream>
 #include<algorithm>
 #include<cmath>
 #include<vector>
 using namespace std;
 const int N = 100+10;
 const double eps = 1e-8;
 const double pi = acos(-1.0);
 inline int dcmp(double x) {
     return x < -eps ? -1 : x > eps;
 }
 inline double sqr(double x) {
     return x * x;
 }
 
 struct Point{
     double x,y;
     Point(){}
     Point(double _x,double _y):x(_x),y(_y){}
     bool operator == (const Point &p) const{
         return dcmp(x - p.x) == 0 && dcmp(y - p.y) == 0;
     }
     Point operator + (const Point &p) const{
         return Point(x + p.x, y + p.y);
     }
     Point operator - (const Point &p) const{
         return Point (x - p.x, y - p.y);
     }
     Point operator * (const double &k) const{
         return Point (x * k, y * k);
     }
     Point operator / (const double &k) const{
         return Point (x / k, y / k);
     }
     double operator * (const Point &p) const{
         return x * p.y - y * p.x;
     }
     double operator / (const Point &p) const{
         return x * p.x + y * p.y;
     }
     double len2() {
         return x * x + y * y;
     }
     double len() {
         return sqrt(len2());
     }
     Point scale(const double &k) {
         return dcmp( len() ) ? (*this) * (k / len()) : (*this);
     }
     Point turnLeft() {
         return Point(-y,x);
     }
     Point turnRight(){
         return Point(y,-x);
     }
     double Distance(const Point &p) {
         return sqrt(sqr(x - p.x) + sqr(y - p.y));
     }
     Point rotate(const Point &p,double angle, double k = 1) {
         Point vec = (*this) - p;
         double c = cos(angle * k)  , s =sin(angle * k) ;
         return p + Point(vec.x * c - vec.y * s, vec.x * s + vec.y * c);
     }
     void input(){
         scanf("%lf%lf",&x,&y);
     }
     void ot() {
         printf("%.3lf %.3lf\n",x,y);
     }
 };
 double Angle(Point a,Point b) {
     return (a/b) / a.len() / b.len();
 }
 struct Line{
     Point a,b;
     Line(){}
     Line(Point a,Point b):a(a),b(b){}
     double operator * (const Point &p) const{
         return (b - a) * (p - a);
     }
     double operator / (const Point &p) const{
         return (p - a) / (p - b);
     }
     bool IsPointOnSeg(const Point &p) {
         return dcmp( (a - p) * (b - p) ) == 0 && dcmp( (p - a) / (p - b) ) <= 0;
     }
     int LineCrossSeg(const Line &v) {//2jiao, 1 dian ,0 wu
         int d1 = dcmp( (*this) * v.a), d2 = dcmp((*this) * v.b);
         if ((d1 ^ d2) == -2) return 2;
         return (d1 == 0 || d2 == 0);
     }
     Point CrossPoint(const Line &v) {
         double s1 = v * a, s2 = v * b;
         return ( a * s2 - b * s1 ) / (s2 - s1);
     }
 };
 Line li[3];
 int d[3];
 Point a[3],b[3],c[3];
 Point st,en;
 
 double u;
 int check(int i) {
     if (dcmp( (li[i].b - li[i].a) * (a[d[i]] - li[i].a) ) > 0) {
         return 1;
     }
     return 0;
 }
 void init(){
     for (int i = 0; i < 3; i++) {
         if (check(i)) {
             b[i] = (li[i].b - li[i].a).turnLeft();
             c[i] = (li[i].b - li[i].a).turnRight();
         }else {
             b[i] = (li[i].b - li[i].a).turnRight();
             c[i] = (li[i].b - li[i].a).turnLeft();
         }
     }
 }
 int ond(Point a,Point b,Point p) {
     if (dcmp((p - a) / (b - a)) >= 0) return 1;
     return 0;
 }
 int step1() {
     int fg = 0;
     Line line = Line(st,en);
     for (int i = 0; i < 3; i++) {
         if (line.LineCrossSeg(li[i]) == 2) {
             Point p = line.CrossPoint(li[i]);
             if (ond(st,en,p)) fg = 1;
         }
     }
     if (fg == 0) {
 
         Point p = line.CrossPoint(Line(Point(0,0),Point(1,0)));
         if (ond(st,en,p)) printf("%.3lf\n",p.x+eps);
         else printf("Error\n");
         return 0;
     }
     return 1;
 
 }
 void findPoint(Point &p,int &id) {
     Line line = Line(st,en);
     double dis = 1e50;
     for (int i = 0; i < 3; i++) {
         if (line.LineCrossSeg(li[i])) {
             Point tp = line.CrossPoint(li[i]);
             if (!ond(st,en,tp)) continue;
             double tdis = tp.Distance(st);
             if (tdis < dis && dcmp(tdis) != 0) {
                 dis = tdis;
                 p = tp;
                 id = i;
             }
         }
     }
 }
 void step2() {
     Point p;
     int id = -1;
     findPoint(p,id);
     Point vec = en - st;
     double cs = Angle(vec,b[id]);
     double sn1 = sqrt(1 - cs * cs);
     double sn2 = sn1 / u;
     double ag = asin(sn1) - asin(sn2);
     if (dcmp(vec * b[id]) <= 0) {
         vec = (p + vec).rotate(p,-ag);
     }else vec = (p + vec).rotate(p,ag);
     st = p; en = vec;
 }
 void step3() {
     Point p;
     int id = -1;
     findPoint(p,id);
     Point vec = en - st;
     double cs = Angle(vec,c[id]);
     double sn1 = sqrt(1 - cs * cs);
     double sn2 = sn1 * u;
     if (sn2 > 1) {
         if (dcmp(p.y) == 0) printf("%.3lf\n",p.x+eps);
         else printf("Error\n");
         return;
     }
     double ag = asin(sn2) - asin(sn1);
     if (dcmp(vec * c[id]) >= 0) {
         vec = (p + vec).rotate(p,-ag);
     }else vec = (p + vec).rotate(p,ag);
     st = p; en = vec;
     Point an = Line(st,en).CrossPoint(Line(Point(0,0),Point(1,0)));
     if (ond(st,en,an)) {
         printf("%.3lf\n",an.x+eps);
     }else printf("Error\n");
 }
 void solve(){
     init();
     if (!step1()) return;
     step2();
     step3();
 }
 int main(){
    // cout<<Line(Point(0,0),Point(1,0)).LineCrossSeg(Line(Point(0,0),Point(1,0)))<<endl;
     int T; scanf("%d",&T);
     while (T--) {
         st.input(); en.input();
         for (int i = 0; i < 3; i++) a[i].input();
         li[0] = Line(a[0],a[1]); d[0] = 2;
         li[1] = Line(a[1],a[2]); d[1] = 0;
         li[2] = Line(a[2],a[0]); d[2] = 1;
         scanf("%lf",&u);
         solve();
     }
     return 0;
 }
 /*
 3
 0 10
 0 20
 -1 3 1 2 -1 1
 1.325
 0 10
 0 0
 -1 3 1 2 -1 1
 1.325
 
 0 10 0 9
 0 0 0 1 1 0
 1.0
 */

 

参考:http://www.cnblogs.com/Rlemon/archive/2013/10/30/3398254.html


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮