P1696 [USACO18JAN] Blocked Billboard II B 题解

· · 题解

怎么题解区都是暴力，来点不一样的做法。

第二个矩形在第一个矩形上方，那么它覆盖的有效度只有以下可能：

  1. 第二个矩形对结果没有任何贡献，题面中的大布仍然要盖住整个第一个矩形。

  1. 第二个矩形成功盖住了第一个矩形的一条边，大布只需要盖住剩下的面积。

  1. 第二个矩形很大，能直接盖住第一个矩形。那么此时不需要大布，那就输出 0。

可以看到，大布面积不需要达到第一个矩形那么大的可能性比较小，可以直接从后到前判断当前两个矩形的状态，然后输出对应的答案。

1. 第二个矩形完全包含第一个矩形

题面中没有给第二个矩形的坐标标号，那就仿照第一个矩形的坐标把输入的四个变量命名成 x_1',y_1',x_2',y_2' 好了。

此时知道第一个矩形（小矩形）两条竖线的 x 坐标分别是 x_1,x_2，第二个矩形（大矩形）两条竖线的 x 坐标分别是 x_1',x_2'，设 x_1<x_2,x_1'<x_2'，那么根据上面的图片可以看到此时必须满足 x_1'\le x_1<x_2\le x_2'，同理，还要满足 y_1'\le y_1<y_2\le y_2'。如果这两个条件同时满足，那么就是第二个矩形完全包含第一个矩形的情况，输出 0。

if(x1_<=x1 && x2<=x2_ && y1_<=y1 && y2<=y2_) cout<<0,exit(0);

2. 第二个矩形能够完全包含第一个矩形的一条边

有如下四种可能。

其实这四种差不多，分析完第一种，就能同理得出剩下三种可能的判断方法和答案。

分析第一种，可以发现它要求第二个矩形的上下两边要夹住第一个矩形的上下两边，即 y_1'\le y_1<y_2\le y_2'。接下来看图可得，第二个矩形的左边那条边在第一个矩形左右两边之间，而第二个矩形右边那条边在第一个矩形右边那条边的右边。所以此时 x_1<x_1'<x_2\le x_2'。

判断出现在两个矩形属于这种情况之后，还需要输出大布的最小面积。此时大布需要完全盖住露出来的那个绿色区域。这个区域左边那条边是第一个矩形左边那条边，即 x 坐标是 x_1 的那条边，右边那条边是第二个矩形左边那条边，即 x 坐标是 x_1' 的那条边，上面那条边和下面那条边跟第一个矩形一样，即它们 y 坐标分别为 y_2 和 y_1。最后输出的答案应该是 (x_1'-x_1)\times(y_2-y_1)。

剩下三个也可以同理推出：

if(x1<x1_ && x1_<x2 && x2<=x2_ && y1_<=y1 && y2<=y2_) cout<<(x1_-x1)*(y2-y1),exit(0);
if(x1_<=x1 && x2<=x2_ && y1<y1_ && y1_<y2 && y2<=y2_) cout<<(x2-x1)*(y1_-y1),exit(0);
if(x1_<=x1 && x1<x2_ && x2_<x2 && y1_<=y1 && y2<=y2_) cout<<(x2-x2_)*(y2-y1),exit(0);
if(x1_<=x1 && x2<=x2_ && y1_<=y1 && y1<y2_ && y2_<y2) cout<<(x2-x1)*(y2-y2_),exit(0);

3. 上面两种情况都不是

那就是刚开始讨论的第一种情况，答案是第一个矩形的面积，即 (x_2-x_1)\times(y_2-y_1)。

cout<<(x2-x1)*(y2-y1);

完整代码：

  1. 由题面中“... are the coordinates of the lower-left and upper-right corners of the ...”可以看出，本题已经默认了 x_1<x_2，剩下的变量也一样。但是有的题目并没有给你排好序，需要注意一下。
  2. y0,y1,yn,j0,j1,jn 是 cmath 头文件的函数。如果要避免变量名冲突，可以给 y1 改个名字或者只 #include<iostream>，而不 #include<bits/stdc++.h>。
#include<iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int x1,y1,x2,y2,x1_,y1_,x2_,y2_;
    cin>>x1>>y1>>x2>>y2>>x1_>>y1_>>x2_>>y2_;
    if(x1_<=x1 && x2<=x2_ && y1_<=y1 && y2<=y2_)cout<<0,exit(0);
    if(x1<x1_ && x1_<x2 && x2<=x2_ && y1_<=y1 && y2<=y2_)cout<<(x1_-x1)*(y2-y1),exit(0);
    if(x1_<=x1 && x2<=x2_ && y1<y1_ && y1_<y2 && y2<=y2_)cout<<(x2-x1)*(y1_-y1),exit(0);
    if(x1_<=x1 && x1<x2_ && x2_<x2 && y1_<=y1 && y2<=y2_)cout<<(x2-x2_)*(y2-y1),exit(0);
    if(x1_<=x1 && x2<=x2_ && y1_<=y1 && y1<y2_ && y2_<y2)cout<<(x2-x1)*(y2-y2_),exit(0);
    cout<<(x2-x1)*(y2-y1);
    return 0;
}

相较于平方复杂度的暴力，这份 O(1) 代码的 Pascal 版本获得了本题的最优解。