题解：P12721 [KOI 2021 Round 2] 矩形面积

volatile · 2025-06-07 17:17:35 · 题解

思路

首先很容易发现，如果当前纸的右下角为 (x_1,y_1)，点的坐标为 (x_2,y_2)，且这个点在这张纸内（不包含边界），当且仅当 x_2<x_1 并且 y_2<y_1。

所以可以挑出不在这张纸中的点。当横向切割时，所剩面积为原面积减去下方部分的面积，即 x_1\times{y_1}-y_1\times{(x_1-x_2)}，同理，纵向切割时为 x_1\times{y_1}-x_1\times{(y_1-y_2)}，比较大小，若横向切割比纵向切割所剩面积大或相等，则 x_1 取 x_2，否则 y_1 取 y_2。

最后输出 x_1\times{y_1} 即可。

代码

#include<iostream>
using namespace std;
int main()
{
    int n,c,nx,ny;
    cin>>n>>c;
    nx=ny=n;
    while(c--){
        int x,y;
        cin>>x>>y;
        if(x<nx&&y<ny){
            int a=nx*ny-ny*(nx-x),b=nx*ny-nx*(ny-y);
            if(a>b) nx=x;
            else if(a<b) ny=y;
            else nx=x;
        }
    }
    cout<<nx*ny;
    return 0;
}