hdu1154(求直线与多边形公共距离)

不太好算。。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define N 1010

#define eps 1e-8

struct Node

{

    double x,y;

} p[N],q[N*10];

int n;

bool cmp(Node a,Node b)//排序，从左到右，从下到上

{

    if(abs(a.x-b.x)<eps)

        return a.y<b.y;

    return a.x<b.x;

}

double dist(Node a,Node b)

{

    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

double mulit(Node a,Node c,Node b)//向量ac与向量ab叉乘

{

    return (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);

}

int check(Node a,Node b,Node c,Node d)//判断直线ab与线段cd是否相交

{

    if(mulit(a,c,b)*mulit(a,d,b)<=0)

        return 1;

    return 0;

}

Node get_point(Node a,Node b,Node c,Node d)//求直线ab与线段cd的交点（已证明直线与线段相交，则可以当做两直线）

{

    Node ret=a;

    double t=((a.x-c.x)*(c.y-d.y)-(a.y-c.y)*(c.x-d.x))

    /((a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x));

    ret.x+=(b.x-a.x)*t;

    ret.y+=(b.y-a.y)*t;

    return ret;

}

int checkss(Node a,Node c,Node d)//判断点a是否在线段cd上

{

    if(mulit(a,c,d)!=0)

        return 0;

    if((a.x<c.x&&a.x<d.x)||(a.x>c.x&&a.x>d.x))

        return 0;

    if((a.y<c.y&&a.y<d.y)||(a.y>c.y&&a.y>d.y))

        return 0;

    return 1;

}

int isI(Node a,Node b,Node c,Node d)//判断线段ab和线段cd是否相交（互跨）

{

    if(mulit(a,c,b)*mulit(a,d,b)<=0&&mulit(c,a,d)*mulit(c,b,d)<=0)

        return 1;

    return 0;

}

int checks(Node a)//判断点a是否在多边形内

{

    Node b=a,c,d;

    b.x=1e15;

    int num=0;

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

    {

        c=p[i];

        d=p[i+1];

        if(checkss(a,c,d))

            return 1;

        if(abs(c.y-d.y)<eps)

            continue;

        if(checkss(c,a,b))

        {

            if(c.y>d.y)

                num++;

        }

        else if(checkss(d,a,b))

        {

            if(d.y>c.y)

                num++;

        }

        else if(isI(a,b,c,d))

        {

            num++;

        }

    }

    return num%2;

}

double get_len(Node a,Node b)//求直线与多边形的公共面积

{

    Node c,d;

    int cnt=0;

    for(int i=0; i<n; i++) //求出直线与多边形各边的交点

    {

        c=p[i];

        d=p[i+1];

        if(abs(mulit(a,b,c))<eps&&abs(mulit(a,b,d))<eps)

        {

            q[cnt++]=c;

            q[cnt++]=d;

        }

        else if(check(a,b,c,d))

            q[cnt++]=get_point(a,b,c,d);

    }

    if(cnt==0)

        return 0.0;

    sort(q,q+cnt,cmp);

    int t=1;

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

    {

        c=q[i];

        d=q[i-1];

        if(!(abs(c.x-d.x)<eps&&abs(c.y-d.y)<eps))

            q[t++]=q[i];

    }//去重

    double sum=0.0;

    for(int i=1; i<t; i++)

    {

        c.x=(q[i].x+q[i-1].x)*0.5;

        c.y=(q[i].y+q[i-1].y)*0.5;

        if(checks(c))

            sum+=dist(q[i],q[i-1]);

    }

    return sum;

}

int main()

{

    int m;

    Node a,b;

    while(~scanf("%d %d",&n,&m)&&n&&m)

    {

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

            scanf("%lf %lf",&p[i].x,&p[i].y);

        p[n]=p[0];

        for(int i=0; i<m; i++)

        {

            scanf("%lf %lf %lf %lf",&a.x,&a.y,&b.x,&b.y);

            printf("%.3lfn",get_len(a,b));

        }

    }

    return 0;

}

最后

以上就是俭朴高跟鞋为你收集整理的hdu1154(求直线与多边形公共距离)的全部内容，希望文章能够帮你解决hdu1154(求直线与多边形公共距离)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。