POJ - 2826 An Easy Problem?!(计算几何，好题)

题目链接：点击查看

题目大意：给出两条线段，问组成的容器最多能接多少雨水

题目分析：既然是接雨水，那么肯定只能是漏斗状，很容易排除掉两种情况：

1. 其中有一条线段平行于x轴
2. 两条线段不相交

还有一种比较难想的情况kuangbin大神提到了，那就是封口的情况，对应就是以下三种情况：

单独讨论之后，剩下的情况就一定有解了，直接按照三角形的面积计算就是答案了

注意结果需要加上一个eps防止出现-0.00的情况，我猜的，不加的话会WA，加上就A了，玄学

代码：

#include<iostream>
#include<cstdio> 
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<sstream>
using namespace std;
 
typedef long long LL;
 
const int inf=0x3f3f3f3f;

const int N=60;

const double eps = 1e-8;

int sgn(double x){
	if(fabs(x) < eps)return 0;
	if(x < 0)return -1;
	else return 1;
}

struct Point{
	double x,y;
	Point(){}
	Point(double _x,double _y){
		x = _x;
		y = _y;
	}
	void input(){
		scanf("%lf%lf",&x,&y);
	}
	Point operator -(const Point &b)const{
		return Point(x-b.x,y-b.y);
	}
	//叉积
	double operator ^(const Point &b)const{
		return x*b.y - y*b.x;
	}
	//点积
	double operator *(const Point &b)const{
		return x*b.x + y*b.y;
	}
	//返回两点的距离
	double distance(Point p){
		return hypot(x-p.x,y-p.y);
	}
};

struct Line{
	Point s,e;
	Line(){}
	Line(Point _s,Point _e){
		s = _s;
		e = _e;
	}
	void input(){
		s.input();
		e.input();
	}
	//求线段长度
	double length(){
		return s.distance(e);
	}
	//`两线段相交判断`
	//`2 规范相交`
	//`1 非规范相交`
	//`0 不相交`
	int segcrossseg(Line v){
		int d1 = sgn((e-s)^(v.s-s));
		int d2 = sgn((e-s)^(v.e-s));
		int d3 = sgn((v.e-v.s)^(s-v.s));
		int d4 = sgn((v.e-v.s)^(e-v.s));
		if( (d1^d2)==-2 && (d3^d4)==-2 )return 2;
		return (d1==0 && sgn((v.s-s)*(v.s-e))<=0) ||
			(d2==0 && sgn((v.e-s)*(v.e-e))<=0) ||
			(d3==0 && sgn((s-v.s)*(s-v.e))<=0) ||
			(d4==0 && sgn((e-v.s)*(e-v.e))<=0);
	}
	//`直线和线段相交判断`
	//`-*this line   -v seg`
	//`2 规范相交`
	//`1 非规范相交`
	//`0 不相交`
	int linecrossseg(Line v){
		int d1 = sgn((e-s)^(v.s-s));
		int d2 = sgn((e-s)^(v.e-s));
		if((d1^d2)==-2) return 2;
		return (d1==0||d2==0);
	}
	//`求两直线的交点`
	//`要保证两直线不平行或重合`
	Point crosspoint(Line v){
		double a1 = (v.e-v.s)^(s-v.s);
		double a2 = (v.e-v.s)^(e-v.s);
		return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
	}
	//点到直线的距离
	double dispointtoline(Point p){
		return fabs((p-s)^(e-s))/length();
	}
}l1,l2;

int main()
{
//	freopen("input.txt","r",stdin);
//	ios::sync_with_stdio(false);
	int w;
	cin>>w;
	while(w--)
	{
		l1.input();
		l2.input();
		if(sgn(l1.s.y-l1.e.y)==0||sgn(l2.s.y-l2.e.y)==0)//有一条线平行于x轴 
		{
			puts("0.00");
			continue;
		}
		if(sgn(l1.s.y-l1.e.y)<0)
			swap(l1.s,l1.e);
		if(sgn(l2.s.y-l2.e.y)<0)
			swap(l2.s,l2.e);
		if(l1.segcrossseg(l2)==0)//不相交 
		{
			puts("0.00");
			continue;
		}
		if(l1.segcrossseg(Line(Point(l2.s.x,100000),l2.s))||l2.segcrossseg(Line(Point(l1.s.x,100000),l1.s)))//口被封上 
		{
			puts("0.00");
			continue;
		}
		double ans1=1e10,ans2=1e10;
		Point point=l1.crosspoint(l2);//交点
		Line temp1=Line(l2.s,Point(100000,l2.s.y));//与x轴平行，且过l2上面的点的直线 
		Line temp2=Line(l1.s,Point(100000,l1.s.y));//与x轴平行，且过l1上面的点的直线 
		if(temp1.linecrossseg(l1))
		{
			Point temp=temp1.crosspoint(l1);//当前三个点构成三角形temp point l2.s 
			ans1=0.5*(temp1.dispointtoline(point)*temp.distance(l2.s));
		}
		if(temp2.linecrossseg(l2))
		{
			Point temp=temp2.crosspoint(l2);//当前三个点构成三角形temp point l1.s 
			ans2=0.5*(temp2.dispointtoline(point)*temp.distance(l1.s));
		}
		printf("%.2f\n",min(ans1,ans2)+eps);
	}
	
	
 
 
 
 
 
 
 
	
	
	
	
	
	
	
	
	
	return 0;
}