自动搬运

查看原文

来自洛谷，原作者为

	volatile 等下次能改名字了，而且橙名了，我就把名字给改掉，看你们还认不认得出我

搬运于2025-08-24 23:17:42，当前版本为作者最后更新于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;
}