矩形交并集

D-现在是，学术时间 (II)_2023牛客寒假算法基础集训营1 (nowcoder.com)

给一个矩形 $(0,0),(x,y)$ 和一个点 $(a,b)$, 再找一个点与 $a,b$ 组成另一个矩形, 求$\frac{交集面积}{并集面积}$ 的最大值。

为了让并集面积尽量小, 新点的选择要从矩形的边中选, 这样就可以直接枚举。然后根据枚举出的点计算两个矩形的交集面积和并集面积求解即可。

并集面积可以在求出交集面积后, 将两个矩形面积相加再减去交集面积。 求交集面积需要先找出 $xl,xr,yl,yr$ 即两个矩形左侧边的最小值, 右侧边的最大值, 上侧边的最小值, 下侧边的最大值。然后再求面积。

#include <bits/stdc++.h>
using namespace std;
int x,y,a,b;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(10) << "\n";
    int T;
    cin >> T;
    while(T--)
    {
 
        double ans = 0;
        cin >> x >> y >> a >> b;
        for(auto c : {0,x})
            for(auto d : {0,y})
            {
                int xl = max(0, min(a,c));
                int xr = min(x, max(a,c));
                int yl = max(0, min(b,d));
                int yr = min(y, max(b,d));
                int inner = abs(xl - xr) * abs(yl - yr);
                int uni = x*y + abs(a-c)*abs(b-d) - inner;
                double res = 1. * inner / uni;
                ans = max(res, ans);
            }
        cout << ans << "\n";
            
    }
    return 0;
}