题意：
在平面直角坐标系中给你N个点，stan和ollie玩一个游戏，首先stan在竖直方向上画一条直线，
该直线必须要过其中的某个点，然后ollie在水平方向上画一条直线，该直线的要求是要经过一个stan画的竖线经过的点。
这时候平面就被分割成了四块，两个人这时候会有一个得分，stan的得分是平面上第1、3象限内的点的个数，
ollie的得分是平面上第2、4象限内的点的个数，在统计的时候所画线上的点都不计算在内。
Stan的策略是，自己画一条竖线之后，Ollie有很多种选择，而ollie当然是让自己的越多越好。
对于Stan画的每条竖线，Stan都有可能获得最小的分数，求这些最小值中的最大值。
并且在该最大值的情况下，输出ollie可能获得的分数。
思路：
这个题目就是把POJ_2352数星星从一个象限拓展到了四个象限，把以每个点为中心四个象限内的点数都计算出来之后，
枚举Stan所划的那条竖线的位置，找出其中Stan所能获得的最小值以及在该最小值情况下Ollie所能获得的最大值，
然后根据实际情况更新结果即可。
具体求四个象限的点的个数，要用到树状数组，具体方法见代码。
注意：
让stan最小值中最大的取法有多种,把每一种中ollie所能取得的最大值算出来就行，而不必求出每一种中Ollie所有可能的取值。
本人写的程序很慢，922ms，在POJ AC的380+人中排名340+。。。
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <vector> using namespace std; const int maxn=200005; const int INF=0x3f3f3f3f; int n; //存储以某点i为中心，它的左上方、右上方、左下方、右下方四个方块中的点的个数，不包括边界上的值。 int upper_left[maxn],upper_right[maxn],bottom_left[maxn],bottom_right[maxn]; //x坐标和y坐标离散的值 int cntx,cnty; int c[maxn]; //树状数组，用于统计四个方向点的个数 vector<int> line[maxn]; //line[i]存储竖线i所经过的点的序号 struct Point{ int x,y; int hx,hy; //x和y离散后的值，从1开始 int idx; //点的序号 }point[maxn]; //将点根据x坐标从小到大排序 bool cmpx(const Point t1,const Point t2){ return t1.x<t2.x; } //将点根据y坐标从小到大排序，若y相同则根据x从小到大排序 bool cmpy(const Point t1,const Point t2){ if(t1.y==t2.y) return t1.x<t2.x; else return t1.y<t2.y; } int lowbit(int x){ return x&(-x); } void update(int i){ while(i<=n){ c[i]++; i+=lowbit(i); } } int sum(int i){ int res=0; while(i){ res+=c[i]; i-=lowbit(i); } return res; } void init(){ for(int i=0;i<=n;i++){ line[i].clear(); } memset(upper_left,0,sizeof(upper_left)); memset(upper_right,0,sizeof(upper_right)); memset(bottom_left,0,sizeof(bottom_left)); memset(bottom_right,0,sizeof(bottom_right)); } int main() { while(scanf("%d",&n)!=EOF){ if(n==0) break; init(); for(int i=1;i<=n;i++){ scanf("%d%d",&point[i].x,&point[i].y); point[i].idx=i; } sort(point+1,point+n+1,cmpx); cntx=1; point[1].hx=cntx; line[cntx].push_back(point[1].idx); //将该点压入对应的竖线中去 for(int i=2;i<=n;i++){ if(point[i].x==point[i-1].x) point[i].hx=point[i-1].hx; else point[i].hx=++cntx; line[point[i].hx].push_back(point[i].idx); } sort(point+1,point+n+1,cmpy); cnty=1; point[1].hy=cnty; for(int i=2;i<=n;i++){ if(point[i].y==point[i-1].y) point[i].hy=point[i-1].hy; else point[i].hy=++cnty; } int num; int samex[maxn]; //存储处于同一横线上，即x坐标相同的点的个数 int samey[maxn]; //存储处于同一竖线上，即y坐标相同的点的个数 memset(samex,0,sizeof(samex)); memset(samey,0,sizeof(samey)); memset(c,0,sizeof(c)); /* 求位于某点“左下方”和“右下方”的点的个数： 按照y从小到大取，当取到某一点a时，那么每次求得的num即是 “x坐标小于a的x坐标，但y坐标可能会有相同的”点的个数， 所以要想求出点位于点a“左下方”的点的个数，还要用num减去“在点a之前加入的与a的y坐标相同”的点的个数， 即samey[point[i].hy]。 同样，在求位于点a“右下方”的点的个数，i-1-num包含了 “x坐标大于等于a的x坐标，y坐标小于a的y坐标”的点的个数， 因此还要用i-1-num减去“在点a之前加入的，与a的x坐标相同的点”的个数，即samex[point[i].hx]。 然后，再更新对应的samex、samey、update */ for(int i=1;i<=n;i++){ num=sum(point[i].hx-1); //注意num求得是“x坐标小于该点的x坐标”的点的个数 bottom_left[point[i].idx]=num-samey[point[i].hy]; bottom_right[point[i].idx]=i-1-num-samex[point[i].hx]; samey[point[i].hy]++; samex[point[i].hx]++; update(point[i].hx); } memset(c,0,sizeof(c)); memset(samex,0,sizeof(samex)); memset(samey,0,sizeof(samey)); /* 求位于某点“左上方和右上方”的点的个数： 这里按照y从到小取，要注意的是当y相同时，先处理的是x较大的点。 当取到某点a时，每次求得的num值是“x坐标小于点a，但y坐标可能会有相同的”点的个数， 但由于当y相同时，取的顺序是按照x坐标从大到小取的，所以对结果并不影响，位于点a的“左上方”的点的个数即为num值。 而在求位于点a的“右上方”的点的个数时，剩余的n-i-num个点为“x坐标大于等于a的x坐标，y大于等于 a的y坐标”的点，所以还要减去“x坐标与a相同”的点的个数，即samex[point[i].hx]，再减去“y坐标与a相同”的点的个数， 即samey[point[i].hy]。 然后，再更新对应的samex、samey、update */ for(int i=n;i>=1;i--){ num=sum(point[i].hx-1); upper_left[point[i].idx]=num; upper_right[point[i].idx]=n-i-num-right[point[i].hx]-left[point[i].hy]; left[point[i].hy]++; right[point[i].hx]++; update(point[i].hx); } int ans=-INF; //stan所能获取的最小值当中的最大值 int sums,sumo; //stan获得的数目，ollie获得的数目 int ollie[maxn],op=-1; //对每条竖线一条一条枚举即可 for(int i=1;i<=cntx;i++){ int minsum=INF,v; int tmp; //ollie能获取的最大值 //对每条竖线上的点枚举 for(int j=0;j<line[i].size();j++){ v=line[i][j]; sums=upper_right[v]+bottom_left[v]; sumo=upper_left[v]+bottom_right[v]; if(sums<minsum){ minsum=sums; tmp=sumo; } else if(sums==minsum){ tmp=max(tmp,sumo); } } if(minsum>ans){ ans=minsum; ollie[0]=tmp; op=0; } else if(minsum==ans){ ollie[++op]=tmp; } } printf("Stan: %d; ",ans); printf("Ollie:"); sort(ollie,ollie+op+1); printf(" %d",ollie[0]); for(int i=1;i<=op;i++){ if(ollie[i]!=ollie[i-1]) printf(" %d",ollie[i]); } printf("; "); } return 0; }