Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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], right[200005];
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;
}