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

时间:2023-03-09 17:46:25
【POJ 2826】An Easy Problem?!(几何、线段)

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

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

求出交点,再取两线段的较高端点的较小值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)<=;//取等号就包括端点在另一线段的情况
}
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()>&&(a.k()-b.k())*(x1-x2)>=;
}
void solve(){
double ans=;
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();
}
}