bzoj4578: [Usaco2016 OPen]Splitting the Field

2365: Splitting the Field

题意:n个点,求用两个矩形面积覆盖完所有点和一个矩形覆盖完少多少面积

思路:枚举两个矩形的分割线,也就是把所有点分成两个部分,枚举分割点;先预处理每个点之前和之后的最大,最低高度;

矩形可以横着分,也可以竖着分

 // #pragma comment(linker, "/STACK:102c000000,102c000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
// #include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N = ;
const int M = 1e6+;
const int MOD = 1e9+;
#define LL long long
#define LB long double
#define mi() (l+r)>>1
double const pi = acos(-);
const double eps = 1e-;
void fre() {
freopen("in.txt","r",stdin);
}
// inline int r() {
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
// }
struct point{
int x,y;
point(int x_=,int y_=):x(x_),y(y_){}
bool operator < (const point &a) const{
return x==a.x?y<a.y:x<a.x;
}
}p[N];
int l[N],r[N],l1[N],r1[N];
int n;
LL ans;
void work(){
clc(l,inf),clc(r,-inf),clc(l1,inf),clc(r1,-inf);
sort(p+,p+n+);
for(int i=;i<=n;i++){
l[i]=min(l[i-],p[i].y),r[i]=max(r[i-],p[i].y);
}
for(int i=n;i>=;i--){
l1[i]=min(l1[i+],p[i].y),r1[i]=max(r1[i+],p[i].y);
}
for(int i=;i<=n;i++){
LL tem=(LL)(r[i-]-l[i-])*(p[i-].x-p[].x)+(LL)(r1[i]-l1[i])*(p[n].x-p[i].x);
ans=min(tem,ans);
}
}
int main(){
int minx=inf,miny=inf,maxx=-inf,maxy=-inf;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d%d",&p[i].x,&p[i].y);
minx=min(minx,p[i].x);
maxx=max(maxx,p[i].x);
miny=min(miny,p[i].y);
maxy=max(maxy,p[i].y);
}
ans=(LL)(maxx-minx)*(maxy-miny);
LL ans1=ans;
work();
for(int i=;i<=n;i++) swap(p[i].x,p[i].y);
work();
printf("%lld\n",ans1-ans);
return ;
}
上一篇:中国本土管理咨询公司排名TOP50


下一篇:【转】redis 消息队列发布订阅模式spring boot实现