首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【POJ 2826】An Easy Problem?!(几何、线段)

【POJ 2826】An Easy Problem?!(几何、线段)

作者头像
饶文津
发布2020-06-02 15:42:49
3190
发布2020-06-02 15:42:49
举报
文章被收录于专栏:饶文津的专栏饶文津的专栏

两个木条装雨水能装多少。

两线段相交,且不遮盖的情况下才可能装到水。

求出交点,再取两线段的较高端点的较小值h,(h-交点的y)为三角形的高。

三角形的宽即为(h带入两条线段所在直线得到的横坐标的差值)。

三角形的面积即为雨水的量。

坑点:如果用G++提交,ans要加上eps才能过,c++提交则没问题。

#include <iostream>
#include <cmath>
#include <cstdio>
#define MAX 1<<31
#define dd double
using namespace std;
struct P {dd x,y;};
struct L{
    P s,e;
    void input(){
        scanf("%lf%lf%lf%lf",&s.x,&s.y,&e.x,&e.y);
        if(s.x>e.x)swap(s,e);
    }
    dd k(){//斜率
        if(s.x==e.x)return MAX;
        return (s.y-e.y)/(s.x-e.x);
    }
    dd highX(){//较高端点的x值
        if(s.y>e.y)return s.x;
        return e.x;
    }
}a,b;
dd xmult(P a,P b,P o){//叉积
    return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}
bool isCross(L a,L b){//是否相交
    return xmult(a.s,a.e,b.s)*xmult(a.s,a.e,b.e)<=0;//取等号就包括端点在另一线段的情况
}
P getCross(L a,L b){
    P c;
    dd ka=a.k(),kb=b.k();
    if(ka==MAX){//a是竖直的
        c.x=a.s.x;
        c.y=(c.x-b.s.x)*kb+b.s.y;
    }
    else{
        if(kb==MAX)
            c.x=b.s.x;
        else
            c.x=(a.s.y-b.s.y-ka*a.s.x+kb*b.s.x)/(kb-ka);
        c.y=(c.x-a.s.x)*ka+a.s.y;
    }
    return c;
}
dd getx(L a,dd y){//a所在直线上纵坐标为y的点的x
    if(a.s.y==a.e.y)return a.s.x;
    return (y-a.s.y)*(a.s.x-a.e.x)/(a.s.y-a.e.y)+a.s.x;
}
bool shadow(L a,L b){//是否遮盖
    dd x1=a.highX(),x2=b.highX();
        //如果倾斜方向一样,k大的线段的较高端点的x也更大则遮盖了
        //并且斜率相同的线段也会返回true
    return a.k()*b.k()>0&&(a.k()-b.k())*(x1-x2)>=0;
}
void solve(){
    double ans=0;
    if(a.k()&&b.k()&&isCross(a,b)&&isCross(b,a)&&!shadow(a,b)){
        P c=getCross(a,b);
        dd h=min(max(a.s.y,a.e.y),max(b.s.y,b.e.y));
        dd w=fabs(getx(a,h)-getx(b,h));
        ans=(h-c.y)*w/2.0;
    }
    printf("%.2f\n",ans);
}
int main() {
    int t;
    cin>>t;
    while(t--){
        a.input();
        b.input();
        solve();
    }
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016-07-31 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档