POJ 2074 /// 判断直线与线段相交视野盲区

题目大意：

将所有物体抽象成一段横向的线段

给定房子的位置和人行道的位置

接下来给定n个障碍物的位置

位置信息为（x1,x2,y）即x1-x2的线段 y相同因为是横向的

求最长的能看到整个房子的一段人行道的长度

若不在 y(房子)和y(人行道)之间的不会有视野的阻碍

注意边界处理因为盲区可能包含在人行道内也可能超出

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

const double eps=1e-;

double add(double a,double b) {

    if(abs(a+b)<eps*(abs(a)+abs(b))) return ;

    return a+b;

}

struct P {

    double x,y;

    P(){};

    P(double _x,double _y):x(_x),y(_y){};

    P operator - (P p) {

        return P(add(x,-p.x),add(y,-p.y)); }

    P operator + (P p) {

        return P(add(x,p.x),add(y,p.y)); }

    P operator * (double d) {

        return P(x*d,y*d); }

    double dot(P p) {

        return add(x*p.x,y*p.y); }

    double det(P p) {

        return add(x*p.y,-y*p.x); }

};

struct Line{

    P s,e;

    Line(){};

    Line(P _s,P _e):s(_s),e(_e){};

}H, L, p[];

bool cmp(Line a,Line b) {

    if(a.s.x==b.s.x) return a.e.x<b.e.x;

    return a.s.x<b.s.x;

}

// 求直线ab与直线cd的交点

P ins(P a,P b,P c,P d) {

    return a+(b-a)*((d-c).det(c-a)/(d-c).det(b-a));

}

// 判断c点是否在线段ab上

bool onSeg(P a,P b,P c) {

    return (a-c).det(b-c)== && (a-c).dot(b-c)<=;

}

int main()

{

    double a,b,c;

    while(~scanf("%lf%lf%lf",&a,&b,&c)) {

        if(a== && b== && c==) break;

        H.s.x=a, H.e.x=b, H.s.y=H.e.y=c; // 房子

        scanf("%lf%lf%lf",&a,&b,&c);

        L.s.x=a, L.e.x=b, L.s.y=L.e.y=c; // 人行道

        int n,cnt=; scanf("%d",&n);

        double up=max(H.s.y,L.s.y);

        double dw=min(H.s.y,L.s.y);

        for(int i=;i<n;i++) {

            scanf("%lf%lf%lf",&a,&b,&c);

            if(c>=up || c<=dw) continue;

            // 不在房子和人行道之间的范围 不会有影响

            p[cnt].s.x=a, p[cnt].e.x=b;

            p[cnt].s.y=p[cnt].e.y=c; cnt++;

        }

        sort(p,p+cnt,cmp);

        double lastX=L.s.x, ans=;

        for(int i=;i<cnt;i++) {

            P x1=ins(H.e,p[i].s,L.s,L.e);

            // 房子右端连障碍左端 与 人行道 的交点

            P y1=ins(H.s,p[i].e,L.s,L.e);

            // 房子左端连障碍右端 与 人行道 的交点

            if(onSeg(L.s,L.e,x1))

                ans=max(ans,x1.x-lastX);

            // 盲区为x1-y1 若这段盲区的起点在人行道上

            // 那么盲区左端之前存在一段 更新答案

            lastX=max(lastX,y1.x);

            // 下一段的开端是位于盲区的右端

        }

        if(lastX<L.e.x) ans=max(ans,L.e.x-lastX);

        // 最后一段盲区位于人行道内 那么盲区之后还有一段

        if(ans) printf("%.2f\n",ans);

        else printf("No View\n");

    }

    return ;

}

/*discuss里的大神们提供的经典测试数据

2 6 6

0 15 0

3

1 2 1

3 4 1

12 13 1

1 5 5

0 10 0

1

0 15 1

2 6 6

0 15 0

3

1 2 1

3 4 1

12 13 1

2 6 6

0 15 0

4

1 2 1

3 4 1

12 13 1

1 5 2

2 6 6

0 15 0

2

0 5 3

6 15 3

2 6 6

0 15 0

2

6 10 1

0 2 1

2 6 6

0 15 0

1

2 6 7

2 6 6

0 15 0

1

4 4.5 5.5

2 6 6

0 15 0

16

0 1 3

1.5 2 3

2.5 3 3

3.5 4 3

4.5 5 3

5.5 6 3

6.5 7 3

7.5 8 3

8.5 9 3

9.5 10 3

10.5 11 3

11.5 12 3

12.5 13 3

13.5 14 3

14.5 15 3

15.5 16 3

2 6 6

0 15 0

16

0 1 .1

1.5 2 .1

2.5 3 .1

3.5 4 .1

4.5 5 .1

5.5 6 .1

6.5 7 .1

7.5 8 .1

8.5 9 .1

9.5 10 .1

10.5 11 .1

11.5 12 .1

12.5 13 .1

13.5 14 .1

14.5 15 .1

15.5 16 .1

2 6 6

0 15 0

14

0 1 3

1.5 2 3

2.5 3 3

3.5 4 3

4.5 5 3

5.5 6 3

8.5 9 3

9.5 10 3

10.5 11 3

11.5 12 3

12.5 13 3

13.5 14 3

14.5 15 3

15.5 16 3

2 6 6

0 4000000000 0

2

1 2 1

15 16 3

2 6 6

0 15 1

5

1 1.5 6

17 18 1

3 5 3

0 20 10

0 20 0.5

*//*

答案：

8.80

No View

8.80

6.70

No View

4.00

15.00

No View

No View

0.44

1.00

3999999970.00

8.00

*/

巴特西

POJ 2074 /// 判断直线与线段相交视野盲区

最新文章

热门文章

巴特西

POJ 2074 /// 判断直线与线段相交 视野盲区

最新文章

热门文章

POJ 2074 /// 判断直线与线段相交视野盲区