LA 3695 Distant Galaxy 扫描线 -

题目地址：http://vjudge.net/problem/UVALive-3695

思路来自刘汝佳

矩形的每条边上肯定会有个点

题意的矩形是指水平，竖直边组成的矩形，并非斜的

那么可以根据点枚举矩形的所有边然后得出最大值

但是这样的时间复杂度有n^5,所以可以枚举上下两条边，通过记忆化递推，得出最大值

那么问题转化为 对于一个已经固定上下边界的矩形，求出最大值

那么可以想到扫描线的方法，从左到右对每一个在上下边界内的点进行扫描，记录，得出最大值

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=100+5,INF=0x3f3f3f3f;
struct Point
{int x,y;bool operator < (const Point& p) const{return x<p.x;}
}p[maxn];
int y[maxn],N,Left[maxn],on[maxn],on2[maxn];
int solve(){sort(p+1,p+N+1);sort(y+1,y+N+1);int m=unique(y+1,y+N+1)-y;if(m<=2) return N;int ans=0;REP(i,1,m-1) REP(j,i+1,m-1){      //枚举上下边界int ymin=y[i],ymax=y[j];int n=0;REP(k,1,N) {              //枚举每一个点，推出Left，on，on2的值if(k==1||p[k].x!=p[k-1].x){  //新的竖线++n;             on[n]=on2[n]=0;Left[n]=k==1?0:Left[n-1]+on2[n-1]-on[n-1];}if(p[k].y>ymin&&p[k].y<ymax) on[n]++;if(p[k].y>=ymin&&p[k].y<=ymax) on2[n]++;}if(n<=2) return N;int M=0;REP(k,1,n){ans=max(ans,Left[k]+on2[k]+M);M=max(M,on[k]-Left[k]);}}return ans;
}
int main(int argc, char const *argv[])
{int kase=0;while(scanf("%d",&N)==1&&N){REP(i,1,N){scanf("%d%d",&p[i].x,&p[i].y);y[i]=p[i].y;}printf("Case %d: %d\n",++kase,solve());}return 0;
}