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

POJ 2826 An Easy Problem?! (计算几何)

程序员文章站 2022-04-02 10:06:38
...

题意:两根木棒,给出两者位置,求能接多少雨水。
POJ 2826 An Easy Problem?! (计算几何)
题解:计算几何
太多注意的点了,以至于代码改了好多遍很乱。
说一下wa的点
①可能重合
②输出结果+eps
③没考虑如下情况
POJ 2826 An Easy Problem?! (计算几何)
剩下的就是比较大小,叉积求面积。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 1010;
//Compares a double to zero
int sgn(double x) {
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    else return 1;
}

//POINT
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;
    }
};

//LINE
struct Line {
    Point s, e;
    Line() {}
    Line(Point _s, Point _e) {
        s = _s;
        e = _e;
    }
    //返回直线倾斜角 0<=angle<pi
    double angle() {
        double k = atan2(e.y - s.y, e.x - s.x);
        if (sgn(k) < 0)k += pi;
        if (sgn(k - pi) == 0)k -= pi;
        return k;
    }
    //两线段相交判断
    //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);
    }
    //点和直线关系
    //1 在左侧
    //2 在右侧
    //3 在直线上
    int relation(Point p) {
        int c = sgn((p - s) ^ (e - s));
        if (c < 0)return 1;
        else if (c > 0)return 2;
        else return 3;
    }
    //两向量平行 (对应直线平行或重合)
    bool parallel(Line v) {
        return sgn((e - s) ^ (v.e - v.s)) == 0;
    }
    //两直线关系
    //0 平行
    //1 重合
    //2 相交
    int linecrossline(Line v) {
        if ((*this).parallel(v))
            return v.relation(s) == 3;
        return 2;
    }
    //求两直线的交点
     //要保证两直线不平行或重合
    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));
    }
};
int n;
double xa1, ya1, xb1, yb1, xa2, ya2, xb2, yb2, xl, yl, xr, yr;
int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%lf%lf%lf%lf", &xa1, &ya1, &xb1, &yb1);
        Line a = Line(Point(xa1, ya1), Point(xb1, yb1));
        scanf("%lf%lf%lf%lf", &xa2, &ya2, &xb2, &yb2);
        Line b = Line(Point(xa2, ya2), Point(xb2, yb2));
        if (a.segcrossseg(b) == 0 || a.linecrossline(b) == 1) puts("0.00");
        else {
            if (a.angle() == 0 || b.angle() == 0) puts("0.00");
            else {
                if (ya1 > yb1) xl = xa1, yl = ya1;
                else xl = xb1, yl = yb1;
                if (ya2 > yb2) xr = xa2, yr = ya2;
                else xr = xb2, yr = yb2;
                if (a.angle() < pi / 2 && b.angle() < pi / 2) {
                    if (a.angle() > b.angle() && xl >= xr && yl >= yr) { puts("0.00"); continue; }
                    if (a.angle() < b.angle() && xl <= xr && yl <= yr) { puts("0.00"); continue; }
                    Point cr = a.crosspoint(b);
                    int miny, minx;
                    Line seg;
                    if (yl < yr) miny = yl, minx = xl, seg = b;
                    else miny = yr, minx = xr, seg = a;
                    Line heng = Line(Point(minx, miny), Point(minx + 1, miny));
                    Point cr2 = heng.crosspoint(seg);
                    Point cr3;
                    if (minx == xl) cr3 = Point(xl, yl);
                    else cr3 = Point(xr, yr);
                    double temp = (cr2.x - cr.x) * (cr3.y - cr.y) - (cr3.x - cr.x) * (cr2.y - cr.y);
                    printf("%.2f\n", fabs(temp) / 2);
                }
                else if (a.angle() > pi / 2 && b.angle() > pi / 2) {
                    if (a.angle() > b.angle() && xl >= xr && yl <= yr) { puts("0.00"); continue; }
                    if (a.angle() < b.angle() && xl <= xr && yl >= yr) { puts("0.00"); continue; }
                    Point cr = a.crosspoint(b);
                    int miny, minx;
                    Line seg;
                    if (yl < yr) miny = yl, minx = xl, seg = b;
                    else miny = yr, minx = xr, seg = a;
                    Line heng = Line(Point(minx, miny), Point(minx + 1, miny));
                    Point cr2 = heng.crosspoint(seg);
                    Point cr3;
                    if (minx == xl) cr3 = Point(xl, yl);
                    else cr3 = Point(xr, yr);
                    double temp = (cr2.x - cr.x) * (cr3.y - cr.y) - (cr3.x - cr.x) * (cr2.y - cr.y);
                    printf("%.2f\n", fabs(temp) / 2);
                }
                else {
                    Point cr = a.crosspoint(b);
                    int miny, minx;
                    Line seg;
                    if (yl < yr) miny = yl, minx = xl, seg = b;
                    else miny = yr, minx = xr, seg = a;
                    Line heng = Line(Point(minx, miny), Point(minx + 1, miny));
                    Point cr2 = heng.crosspoint(seg);
                    Point cr3;
                    if (minx == xl) cr3 = Point(xl, yl);
                    else cr3 = Point(xr, yr);
                    double temp = (cr2.x - cr.x) * (cr3.y - cr.y) - (cr3.x - cr.x) * (cr2.y - cr.y);
                    printf("%.2f\n", fabs(temp) / 2);
                }
            }
        }
    }
	return 0;
}