蒟蒻求助,t了4个点(玄关!
查看原帖
蒟蒻求助,t了4个点(玄关!
1216461
cthulhufthagn楼主2025/7/29 10:49

rt

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,ans=1e18,l[50010],r[50010],l1[50010],r1[50010];
struct Node{
	int x,y;
}a[50010];
bool cmp(Node a,Node b){
	if(a.x!=b.x) return a.x<b.x;
	return a.y<b.y;
}
void solve(){
	memset(l,0x3f,sizeof l),memset(l1,0x3f,sizeof l1),memset(r,0,sizeof r),memset(r1,0,sizeof r1);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) l[i]=min(l[i-1],a[i].y),r[i]=max(r[i-1],a[i].y);
	for(int i=n;i>=1;i--) l1[i]=min(l1[i+1],a[i].y),r1[i]=max(r1[i+1],a[i].y);
	for(int i=2;i<=n;i++){
		ans=min(ans,(a[i-1].x-a[1].x)*(r[i-1]-l[i-1])+(a[n].x-a[i].x)*(r1[i]-l1[i]));
	}
}
int maxx=-1e18,minx=1e18,maxy=-1e18,miny=1e18;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&a[i].x,&a[i].y);
		maxx=max(maxx,a[i].x),maxy=max(maxy,a[i].y);
		minx=min(minx,a[i].x),miny=min(miny,a[i].y);
	}
	for(int i=1;i<=n;i++) 
	solve();
	for(int i=1;i<=n;i++) swap(a[i].x,a[i].y);
	solve();
	int s=(maxx-minx)*(maxy-miny);
	printf("%lld\n",s-ans);
	return 0;
}

2025/7/29 10:49
加载中...