平面之角坐标系中现有一矩形(0,0)(x,y)

目标检测

题目描述

平面之角坐标系中现有一矩形 $A$，其左下角和右上角坐标分别为 $(0,0),(x,y)$。

坐标系中另有一点 $M(x_m, y_m)$，请你计算所有以该点作为任一顶点且所有边都平行于坐标轴的矩形中，与矩形 $A$ 能形成的最大 $K$ 值为多少。

两个图形的 $K$ 值的定义为：$交集面积 / 并集面积$。

输入格式

输入的第一行，包含一个整数 $T$，表示测试样例的组数。

每组测试样例，包含四个整数 $x, y, x_m, y_m$。

输出格式

每组测试用例，输出该组询问的答案，结果保留两位小数。

样例 #1

样例输入 #1

3
3 4 1 2
3 4 5 5
3 4 1 5

样例输出 #1

0.33
0.48
0.57

提示

$1 \leq T \leq 10^4$

$1 \leq x,y,x_m,y_m \leq 10^3$

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

const double eps = 1e-8;  // 精度

// 判断两个实数是否相等
int dcmp(double x)
{
    if (fabs(x) < eps)
        return 0;
    else
        return x < 0 ? -1 : 1;
}

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}

    // 重载 +, -, *, / 运算符
    Point operator + (const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator - (const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator * (double d) const { return Point(x * d, y * d); }
    Point operator / (double d) const { return Point(x / d, y / d); }

    // 重载比较运算符
    bool operator < (const Point& p) const {
        return dcmp(x - p.x) == 0 ? dcmp(y - p.y) < 0 : x < p.x;
    }

    // 判断两个点是否相等
    bool operator == (const Point& p) const {
        return dcmp(x - p.x) == 0 && dcmp(y - p.y) == 0;
    }
};

typedef Point Vector;

// 计算向量的长度
double getLength(Vector v)
{
    return sqrt(v.x * v.x + v.y * v.y);
}

// 计算向量的点积
double getDot(Vector A, Vector B)
{
    return A.x * B.x + A.y * B.y;
}

// 计算向量的叉积
double getCross(Vector A, Vector B)
{
    return A.x * B.y - A.y * B.x;
}

// 计算两条线段的交点
// 如果不存在交点，返回 Point(-INF, -INF)
Point getIntersection(Point P, Vector v, Point Q, Vector w)
{
    Vector u = P - Q;
    double t = getCross(w, u) / getCross(v, w);
    return P + v * t;
}

// 计算三角形的面积
double getTriangleArea(Point A, Point B, Point C)
{
    Vector AB = B - A, AC = C - A;
    return fabs(getCross(AB, AC)) / 2.0;
}

// 计算三角形 ABC 与矩形 A 的交集面积
double getTriangleIntersectionArea(Point A, Point B, Point C, Point x, Point y)
{
    Point M = getIntersection(A, B - A, x, Vector(0, 1));
    Point N = getIntersection(B, C - B, y, Vector(-1, 0));
    Point O = getIntersection(A, C - A, x, Vector(0, -1));
    Point P = getIntersection(C, B - C, y, Vector(1, 0));
    if (M == Point(-1e15, -1e15) || N == Point(-1e15, -1e15) ||
        O == Point(-1e15, -1e15) || P == Point(-1e15, -1e15))  // 无交点
        return 0