欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-04 08:22:14
...

题目链接:点击查看

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

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

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

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

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

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

注意结果需要加上一个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;
}

 

相关标签: 几何 计算几何