题意：
在平面直角坐标系中给你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=;
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=;
while(i){
res+=c[i];
i-=lowbit(i);
}
return res;
} void init(){
for(int i=;i<=n;i++){
line[i].clear();
}
memset(upper_left,,sizeof(upper_left));
memset(upper_right,,sizeof(upper_right));
memset(bottom_left,,sizeof(bottom_left));
memset(bottom_right,,sizeof(bottom_right));
}
int main()
{
while(scanf("%d",&n)!=EOF){
if(n==)
break;
init();
for(int i=;i<=n;i++){
scanf("%d%d",&point[i].x,&point[i].y);
point[i].idx=i;
}
sort(point+,point+n+,cmpx);
cntx=;
point[].hx=cntx;
line[cntx].push_back(point[].idx); //将该点压入对应的竖线中去
for(int i=;i<=n;i++){
if(point[i].x==point[i-].x)
point[i].hx=point[i-].hx;
else
point[i].hx=++cntx;
line[point[i].hx].push_back(point[i].idx);
}
sort(point+,point+n+,cmpy);
cnty=;
point[].hy=cnty;
for(int i=;i<=n;i++){
if(point[i].y==point[i-].y)
point[i].hy=point[i-].hy;
else
point[i].hy=++cnty;
} int num;
int samex[maxn]; //存储处于同一横线上，即x坐标相同的点的个数
int samey[maxn]; //存储处于同一竖线上，即y坐标相同的点的个数
memset(samex,,sizeof(samex));
memset(samey,,sizeof(samey));
memset(c,,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=;i<=n;i++){
num=sum(point[i].hx-); //注意num求得是“x坐标小于该点的x坐标”的点的个数
bottom_left[point[i].idx]=num-samey[point[i].hy];
bottom_right[point[i].idx]=i--num-samex[point[i].hx];
samey[point[i].hy]++;
samex[point[i].hx]++;
update(point[i].hx);
}
memset(c,,sizeof(c));
memset(samex,,sizeof(samex));
memset(samey,,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>=;i--){
num=sum(point[i].hx-);
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=-;
//对每条竖线一条一条枚举即可
for(int i=;i<=cntx;i++){
int minsum=INF,v;
int tmp; //ollie能获取的最大值
//对每条竖线上的点枚举
for(int j=;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[]=tmp;
op=;
}
else if(minsum==ans){
ollie[++op]=tmp;
}
}
printf("Stan: %d; ",ans);
printf("Ollie:");
sort(ollie,ollie+op+);
printf(" %d",ollie[]);
for(int i=;i<=op;i++){
if(ollie[i]!=ollie[i-])
printf(" %d",ollie[i]);
}
printf(";\n");
}
return ;
}