poj 2826 An Easy Problem?! （变态卡数据题）
题目链接：poj 2826
题意：给出两条直线，水从天上落下，问：这两条直线组成的平面容器能装多少水？
题解：很gou的题，超级变态卡数据，艹，足足搞了我几天，总算搞出来了。
参考链接：https://www.cnblogs.com/kuangbin/p/3192511.html kuangbin神犇的，不过它代码少了一句话，已经加上去了
这种情况是覆盖的，
注意答案要加eps，这是一个好习惯，浮点数运算可能得到-0.00，而测评机不接受负数，要加eps变为0.00。
习惯参考于：https://blog.****.net/wl16wzl/article/details/82107592
至于为什么会这样，目前还不是太清楚，以后再补充，反正我代码答案要不加eps的话，不能AC，kuangbin大佬的不加能AC，可以评测机也势力......
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
struct point{
double x,y;
point(){}
point(double _x,double _y)
{
x=_x;y=_y;
}
};
struct LINE{
point a,b;
LINE(){}
LINE(point _a,point _b){
a=_a;b=_b;
}
};
point operator + (point A, point B) { return point(A.x + B.x, A.y + B.y); }
point operator - (point A, point B) { return point(A.x - B.x, A.y - B.y); }
point operator * (point A, double p) { return point(A.x * p, A.y * p); }
point operator / (point A, double p) { return point(A.x/p, A.y/p); }
bool operator < (const point& a, const point& b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
const double eps = 1e-8;
int dcmp(double x) {
if(fabs(x) < eps) return 0;
else return x < 0 ? -1 : 1;
}
bool operator == (const point& a, const point& b) {
return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}
double Dot(point A, point B) { return A.x * B.x + A.y * B.y; } ///点积
double Cross(point A, point B) { return A.x * B.y - A.y * B.x; } ///叉积
point Getlinenode(point P, point v, point Q, point w) { ///两直线交点（点，向量，点，向量）
// printf("w.x=%f,w.y=%f\n",w.x,w.y);
point u = P - Q;
double t = Cross(w, u) / Cross(v, w);
return P + v * t;
}
bool seg_seg_Cross(point s1,point e1,point s2,point e2)///判断两线段是否相交（不包括端点）
{
///第一步，快速排斥实验
if(!(min(s1.x,e1.x)<=max(s2.x,e2.x)&&min(s2.x,e2.x)<=max(s1.x,e1.x)&&
min(s1.y,e1.y)<=max(s2.y,e2.y)&&min(s2.y,e2.y)<=max(s1.y,e1.y))) return false;
double c1=Cross(s2-s1,e1-s1),c2=Cross(e1-s1,e2-s1);
double c3=Cross(s1-s2,e2-s2),c4=Cross(e2-s2,e1-s2);
if(dcmp(c1*c2)>=0&&dcmp(c3*c4)>=0) return 1;
return 0;
}
bool line_seg_Cross(point s1,point e1,point s2,point e2) ///判断直线与线段相交，s1e1表示直线，s2e2表示线段
{
double c1=Cross(s2-s1,e1-s1),c2=Cross(e1-s1,e2-s1);
///==0表示，相交于端点也认定为相交
if(dcmp(c1*c2)>=0) return true;
return false;
}
int main()
{
int ncase;
double x1,y1,x2,y2,x3,y3,x4,y4;
scanf("%d",&ncase);
LINE l1,l2;
while(ncase--)
{
scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
l1=LINE(point(x1,y1),point(x2,y2));
l2=LINE(point(x3,y3),point(x4,y4));
if(dcmp(y1-y2)==0||dcmp(y3-y4)==0){ ///某一个木板与地面平行
printf("0.00\n");continue;
}
if(dcmp(y1-y2)<0) swap(l1.a,l1.b);
if(dcmp(y3-y4)<0) swap(l2.a,l2.b);
if(seg_seg_Cross(l1.a,l1.b,l2.a,l2.b)==0){ ///两木板没有交点
printf("0.00\n");continue;
}
if(dcmp(Cross(l1.a-l1.b,l2.a-l2.b))==0){ ///两木板平行或重合
printf("0.00\n");continue;
}
///口被l2封掉
if(seg_seg_Cross(l1.a,point(l1.a.x,100000),l2.a,l2.b)){
printf("0.00\n");continue;
}
///口被l1封掉
if(seg_seg_Cross(l2.a,point(l2.a.x,100000),l1.a,l1.b)){
printf("0.00\n");continue;
}
///求面积了
point p=Getlinenode(l1.a,l1.a-l1.b,l2.a,l2.a-l2.b); ///求两木板的交点
///求过l1.a点并与地面平行的直线和直线l2的交点
point p1=Getlinenode(point(100000,l1.a.y),l1.a-point(100000,l1.a.y),l2.a,l2.b-l2.a);
double ans1=fabs(Cross(p1-p,l1.a-p))/2.0;
p1=Getlinenode(point(100000,l2.a.y),l2.a-point(100000,l2.a.y),l1.a,l1.b-l1.a);
double ans2=fabs(Cross(p1-p,l2.a-p))/2.0;
if(dcmp(ans1-ans2)<0) printf("%.2f\n",ans1+eps); ///这里加个eps
else printf("%.2f\n",ans2+eps);
}
return 0;
}
/*
10
0 5 3 0
1 1 3 0
3 0 6 3
3 0 5 1
3 0 6 3
3 0 7 3
0 1 1 0
1 0 2 1
0 1 2 1
1 0 1 2
0 5 3 0
2 5 3 0
*/
再贴下神犇的代码：
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
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;
}
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;
}
};
struct Line
{
Point s,e;
Line(){}
Line(Point _s,Point _e)
{
s = _s;e = _e;
}
//两直线相交求交点
//第一个值为0表示直线重合，为1表示平行，为0表示相交,为2是相交
//只有第一个值为2时，交点才有意义
pair<int,Point> operator &(const Line &b)const
{
Point res = s;
if(sgn((s-e)^(b.s-b.e)) == 0)
{
if(sgn((s-b.e)^(b.s-b.e)) == 0)
return make_pair(0,res);//重合
else return make_pair(1,res);//平行
}
double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
res.x += (e.x-s.x)*t;
res.y += (e.y-s.y)*t;
return make_pair(2,res);
}
};
//*判断线段相交
bool inter(Line l1,Line l2)
{
return
max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&
max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&
max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&
max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&
sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e)) <= 0 &&
sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e)) <= 0;
}
int main()
{
int x1,y1,x2,y2,x3,y3,x4,y4;
int T;
Line l1,l2;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
l1 = Line(Point(x1,y1),Point(x2,y2));
l2 = Line(Point(x3,y3),Point(x4,y4));
if(sgn(l1.s.y-l1.e.y)==0 || sgn(l2.s.y-l2.e.y) == 0)
{
printf("0.00\n");
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(inter(l1,l2) == false)
{
printf("0.00\n");
continue;
}
//口被封掉的情况
if(inter(Line(l1.s,Point(l1.s.x,100000)),l2) )
{
printf("0.00\n");
continue;
}
//口被封掉
if(inter(Line(l2.s,Point(l2.s.x,100000)),l1) )
{
printf("0.00\n");
continue;
}
pair<int,Point>pr;
pr = l1 & l2;
if(pr.first!=2) { ///原代码少了这句话，判断两木板是否平行或重合
printf("0.00\n");continue;
}
Point p = pr.second;
double ans1;
pr = l1 & Line(Point(100000,l2.s.y),l2.s);
Point p1 = pr.second;
ans1 = fabs( (l2.s-p)^(p1-p) )/2;
double ans2;
pr = l2 & Line(Point(100000,l1.s.y),l1.s);
Point p2 = pr.second;
ans2 = fabs( (l1.s-p)^(p2-p) )/2;
printf("%.2lf\n",min(ans1,ans2));
}
return 0;
}