Problem

Solution

把点映射至二维平面，问题就变成了给定 \(n\) 个点，可以把点对 \(y=x\) 对称，求覆盖所有点的最小矩形面积。

可以先把所有点放到 \(y=x\) 下方，那么我们每次只需要贪心地把矩形左/右边界上的点对称过去即可，用multiset维护一下。

正确性在于如果把矩形内部的点对称过去，肯定不会使得当前矩形的面积变小。

时间复杂度 \(O(n\log n)\)。

Code

#include <algorithm>

#include <cstdio>

#include <set>

using namespace std;

typedef long long ll;

const int maxn=200010,INF=0x3f3f3f3f;

template <typename Tp> inline int getmin(Tp &x,Tp y){return y<x?x=y,1:0;}

template <typename Tp> inline int getmax(Tp &x,Tp y){return y>x?x=y,1:0;}

template <typename Tp> inline void read(Tp &x)

{

    x=0;int f=0;char ch=getchar();

    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

    if(ch=='-') f=1,ch=getchar();

    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();

    if(f) x=-x;

}

struct data{

	int x,y;

	bool operator < (const data &b)const{return x<b.x;}

}a[maxn];

int n,mx,mn,bmn=INF;

ll ans=1e18;

multiset<int> A,B;

int main()

{

	read(n);

	for(int i=1;i<=n;i++)

	{

		read(a[i].x);read(a[i].y);

		if(a[i].x>a[i].y) swap(a[i].x,a[i].y);

		getmax(mx,a[i].y);getmin(bmn,a[i].y);

		A.insert(a[i].x);B.insert(a[i].y);

	}

	sort(a+1,a+n+1);

	mn=a[1].x;

	for(int i=1;i<=n;i++)

	{

		A.erase(A.find(a[i].x));

		B.insert(a[i].x);

		B.erase(B.find(a[i].y));

		A.insert(a[i].y);

	  	getmin(ans,(ll)(*A.rbegin()-*A.begin())*(*B.rbegin()-*B.begin()));

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

ARC073E Ball Coloring

Problem

Solution

Code

最新文章

热门文章