978
POJ 2826 兩線段關係求麵積
題意：兩個木板接雨，問你能解多少雨，也就是麵積。
這題考慮幾種情況：1，有線段平行x軸，接不到；2，兩線段沒交點，接不到；3，取兩線段高的端點如果比兩線段交點低也接不到；4，最不容易想到的，兩木板在同側並且上麵的木板蓋住了下麵的木板也接不到。這四條單獨判斷然後求三角形麵積就可以了。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double PointType;
struct point
{
PointType x,y;
};
PointType Direction(point pi,point pj,point pk) //判斷向量PiPj在向量PiPk的順逆時針方向 +順-逆0共線
{
return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
bool On_Segment(point pi,point pj,point pk)
{
if(pk.x>=min(pi.x,pj.x)&&pk.x<=max(pi.x,pj.x)&&pk.y>=min(pi.y,pj.y)&&pk.y<=max(pi.y,pj.y))
return 1;
return 0;
}
bool Segment_Intersect(point p1,point p2,point p3,point p4)
{
PointType d1=Direction(p3,p4,p1),d2=Direction(p3,p4,p2),d3=Direction(p1,p2,p3),d4=Direction(p1,p2,p4);
if(((d1>0&&d2<0)||(d1<0&&d2>0))&&((d3>0&&d4<0)||(d3<0&&d4>0)))
return 1;
if(d1==0&&On_Segment(p3,p4,p1))
return 1;
if(d2==0&&On_Segment(p3,p4,p2))
return 1;
if(d3==0&&On_Segment(p1,p2,p3))
return 1;
if(d4==0&&On_Segment(p1,p2,p4))
return 1;
return 0;
}
point jd;
int Jiaodian(point a,point b,point c,point d)//平行返回0 重合返回1 相交返回2
{
double A1=b.y-a.y,A2=d.y-c.y,B1=a.x-b.x,B2=c.x-d.x;
double C1=b.y*(b.x-a.x)-b.x*(b.y-a.y),C2=d.y*(d.x-c.x)-d.x*(d.y-c.y);
if(A1*B2==B1*A2)//平行或重合
{
if(A2*C1==A1*C2&&B1*C2==B2*C1)
return 1;
return 0;
}
jd.x=(B1*C2-B2*C1)/(B2*A1-B1*A2);
jd.y=(A1*C2-A2*C1)/(A2*B1-A1*B2);
return 2;
}
double dis(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int main()
{
int t;
point data[2][2],a,b;
cin>>t;
while(t--)
{
cin>>data[0][0].x>>data[0][0].y>>data[0][1].x>>data[0][1].y;
cin>>data[1][0].x>>data[1][0].y>>data[1][1].x>>data[1][1].y;
if(data[0][0].y==data[0][1].y||data[1][0].y==data[1][1].y)
{
cout<<"0.00"<<endl;
continue;
}
if(!Segment_Intersect(data[0][0],data[0][1],data[1][0],data[1][1]))
{
cout<<"0.00"<<endl;
continue;
}
if(Jiaodian(data[0][0],data[0][1],data[1][0],data[1][1])!=2)
{
cout<<"0.00"<<endl;
continue;
}
a=data[0][0].y>data[0][1].y?data[0][0]:data[0][1];
b=data[1][0].y>data[1][1].y?data[1][0]:data[1][1];
if(jd.y>=a.y||jd.y>=b.y)
{
cout<<"0.00"<<endl;
continue;
}
double disa=dis(a,jd),disb=dis(b,jd);
if(disa<disb)
swap(a,b);
point temp,upjd,upb;
upb.x=b.x,upb.y=9999999;
upjd.x=jd.x,upjd.y=jd.y+1;
double ua=Direction(jd,upjd,a),ub=Direction(jd,upjd,b),uc=Direction(jd,a,b);
if((ua>0&&ub>0&&uc>0||ua<0&&ub<0&&uc<0)&&Segment_Intersect(b,upb,a,jd))
{
cout<<"0.00"<<endl;
continue;
}
a=data[0][0].y>data[0][1].y?data[0][0]:data[0][1];
b=data[1][0].y>data[1][1].y?data[1][0]:data[1][1];
upjd=jd;
if(a.y>=b.y)
{
temp.y=b.y;
temp.x=b.x+1;
Jiaodian(temp,b,data[0][0],data[0][1]);
printf("%.2f\n",fabs(Direction(upjd,b,jd))/2);
}
else
{
temp.y=a.y;
temp.x=a.x+1;
Jiaodian(temp,a,data[1][0],data[1][1]);
printf("%.2f\n",fabs(Direction(upjd,a,jd))/2);
}
}
return 0;
}
最後更新：2017-04-03 22:15:27