Problem E: Brownie Points II
Stan and Ollie play the game of Odd Brownie Points. Some brownie points are located in the plane, at integer coordinates. Stan plays first and places a vertical line in the plane. The line must go through a brownie point and may cross many (with the same x-coordinate). Then Ollie places a horizontal line that must cross a brownie point already crossed by the vertical line. Those lines divide the plane into four quadrants. The quadrant containing points with arbitrarily large positive coordinates is the top-right quadrant.
The players score according to the number of brownie points in the quadrants. If a brownie point is crossed by a line, it doesn't count. Stan gets a point for each (uncrossed) brownie point in the top-right and bottom-left quadrants. Ollie gets a point for each (uncrossed) brownie point in the top-left and bottom-right quadrants.
Stan and Ollie each try to maximize his own score. When Stan plays, he considers the responses, and chooses a line which maximizes his smallest-possible score.
Input contains a number of test cases. The data of each test case appear on a sequence of input lines. The first line of each test case contains a positive odd integer 1 < n < 200000 which is the number of brownie points. Each of the following n lines contains two integers, the horizontal (x) and vertical (y) coordinates of a brownie point. No two brownie points occupy the same place. The input ends with a line containing 0 (instead of the n of a test).
For each input test, print a line of output in the format shown below. The first number is the largest score which Stan can assure for himself. The remaining numbers are the possible (high) scores of Ollie, in increasing order.
Sample input
11 3 2 3 3 3 4 3 6 2 -2 1 -3 0 0 -3 -3 -3 -2 -3 -4 3 -7 0
Output for sample input
Stan: 7; Ollie: 2 3;
P. Rudnicki
目描述：
Stan 和 Ollie 玩一，平面上有，Stan 一垂直後， Ollie 一水平，
必然要交於一，Stan 得分左上右下象限的，Ollie 拿到左下右上的。
而 Stan 玩的候，一可以使得最低得分最高，Ollie 在他後，找到一使得他得分最高。
求 Stan 的得分，以及 Ollie 有可能拿到哪些得分，且由小到大出。
目解法：
入的 y 座散化，以方便藉由 binary indexed tree 查找象限。
BIT，垂直的左和右。
利用描，由左至右描每一，由於得分不算上的。
因此，相同垂直上要同，依序右的，右 BIT 去除，加入左 BIT。
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
struct Pt {
int x, y, dy;
Pt(int a=0, int b=0):
x(a), y(b), dy(0) {}
bool operator<(const Pt &a) const {
if(x != a.x)
return x < a.x;
return y < a.y;
}
};
bool cmp(Pt a, Pt b) {
return a.y < b.y;
}
Pt D[200005];
// binary indexed tree.
void modify(int idx, int val, int n, int C[]) {
while(idx <= n) {
C[idx] += val;
idx += idx&(-idx);
}
}
int query(int idx, int C[]) {
int ret = 0;
while(idx) {
ret += C[idx];
idx -= idx&(-idx);
}
return ret;
}
int left[200005], right200005];
int main() {
int n, m;
int i, j, k;
while(scanf("%d", &n) == 1 && n) {
for(i = 0; i < n; i++)
scanf("%d %d", &D[i].x, &D[i].y);
sort(D, D+n, cmp);
int prevy = D[0].y-1;
for(i = 0, m = 0; i < n; i++) {
if(D[i].y != prevy) {
m++;
prevy = D[i].y;
}
D[i].dy = m;
}
sort(D, D+n);
// pre-process.
memset(right, 0, 4*m+4);
memset(left, 0, 4*m+4);
int rsize = n, lsize = 0;
for(i = 0; i < n; i++) {
modify(D[i].dy, 1, m, right);
}
// start.
int previ = 0;
int stan = -1;
vector<int> olli;
for(i = 1; i <= n; i++) {
if(D[i].x != D[i-1].x || i == n) {//[previ, i-1]
for(j = previ; j < i; j++) {
modify(D[j].dy, -1, m, right);
rsize--;
}
int a, b = -1;
int ta, tb;
for(j = previ; j < i; j++) {
ta = (rsize-query(D[j].dy, right))+query(D[j].dy-1, left);//top-right + bottom-left
tb = (lsize-query(D[j].dy, left))+query(D[j].dy-1, right);//top-left + bottom-right
if(tb > b)
b = tb, a = ta;
if(tb == b)
a = min(a, ta);
}
if(a > stan)
stan = a, olli.clear();
if(a == stan)
olli.push_back(b);
for(j = previ; j < i; j++) {
modify(D[j].dy, 1, m, left);
lsize++;
}
previ = i;
}
}
sort(olli.begin(), olli.end());
vector<int>::iterator it = unique(olli.begin(), olli.end());
olli.resize(distance(olli.begin(), it));
printf("Stan: %d; Ollie:", stan);
for(i = 0; i < olli.size(); i++)
printf(" %d", olli[i]);
puts(";");
}
return 0;
}
文章定位：
