Solution

网上的做法大多是扫描线 + 树状数组,我的做法也差不多,只不过写的是线段树(没他们的短)。
首先可以证明的是不存在永不终止的情况,所以输出 -1 是没分的(垃圾出题人),进一步考虑下可以发现最多变色一次就会把所有点染完色了,如果我们把两个同一行或同一列的两个点看成一个线段,那么染色的点一定就是行列两条线端的交点。

我们只要求线段交点个数就可以了,我们可以用线段树来完成这个问题,遇到横向的边就区间更新 +1,遇到纵向的边就单点查询。看起来有点问题是吧?由于纵向的边是一个线段,我们只能要一定纵坐标范围内的横向边,线段树是无法直接维护这个东西的,所以我们离线所有纵向的查询,把每个查询拆分成两个查询,这样就都是从 1~i 开始的询问了,然后把竖直线的查询按照要查询高度排序,同时把所有横向边排序,然后每次把当前查询的竖直线高度以下的横向边加到线段树里,然后单点查询就可以了。

如果你按我说的做了,那么恭喜你,你 WA 了,因为两条线段的交点不一定能染色,如果两个线段的交点本身已经是个黑点了,那么就重复染色了,所以需要统计下这样点的个数,最后减去。还需要注意的就是线段不包括两个黑色的端点。

离散化是必须的。

Code

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 300000;
int n;
int x[N], y[N];
vector<int> vec;
int id(int x) {
    return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;
}
int tree[N<<2], col[N<<2];
void pushup(int p) {
    tree[p] = tree[p<<1] + tree[p<<1|1];
}
void pushdown(int p, int l, int r) {
    if(!col[p]) return;
    int mid = (l + r) >> 1;
    tree[p<<1] += (mid - l + 1) * col[p];
    tree[p<<1|1] += (r - mid) * col[p];
    col[p<<1] += col[p]; col[p<<1|1] += col[p];
    col[p] = 0;
}
void update(int p, int l, int r, int L, int R, int v) {
    if(L > R) return;
    if(L <= l && r <= R) {
        tree[p] += (r - l + 1) * v;
        col[p] += v;
        return;
    }
    pushdown(p, l, r);
    int mid = (l + r) >> 1;
    if(L <= mid) update(p<<1, l, mid, L, R, v);
    if(R > mid) update(p<<1|1, mid+1, r, L, R, v);
    pushup(p);
}
int query(int p, int l, int r, int pos) {
    if(l == r) return tree[p];
    int mid = (l + r) >> 1;
    pushdown(p, l, r);
    if(pos <= mid) return query(p<<1, l, mid, pos);
    else return query(p<<1|1, mid+1, r, pos);
}
vector<int> a[N], b[N];
struct Line {
    int x, y, h;
    friend bool operator < (Line a, Line b) {
        return a.h < b.h;
    }
};
vector<Line> line;
struct Query {
    int h, id, t, x;
    friend bool operator < (Query a, Query b) {
        return a.h < b.h;
    }
};
vector<Query> quer;
int ans1[N], ans2[N], ce;
int main() {
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        scanf("%d%d", &x[i], &y[i]);
        vec.push_back(x[i]);
        vec.push_back(y[i]);
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for(int i=1; i<=n; i++) {
        x[i] = id(x[i]);
        y[i] = id(y[i]);
    }
    for(int i=1; i<=n; i++) {
        a[y[i]].push_back(x[i]);
        b[x[i]].push_back(y[i]);
    }
    int cnt = 0;
    for(int i=1; i<=2*n; i++) {
        sort(a[i].begin(), a[i].end());
        sort(b[i].begin(), b[i].end());
    }
    for(int i=1; i<=n; i++) {
        if(a[y[i]].size() < 3) continue;
        if(b[x[i]].size() < 3) continue;
        bool f1 = false, f2 = false;
        if(x[i] > a[y[i]][0] && x[i] < a[y[i]][a[y[i]].size()-1]) f1 = true;
        if(y[i] > b[x[i]][0] && y[i] < b[x[i]][b[x[i]].size()-1]) f2 = true;
        cnt += f1 && f2;
    }
    for(int i=1; i<=2*n; i++) {
        if(a[i].size() >= 2) {
            line.push_back((Line){a[i][0]+1, a[i][a[i].size()-1]-1, i});
        }
        if(b[i].size() >= 2) {
            quer.push_back((Query){b[i][0], ++ce, 0, i});
            quer.push_back((Query){b[i][b[i].size()-1]-1, ce, 1, i});
        }
    }
    int p = 0;
    int ans = 0;
    sort(quer.begin(), quer.end());
    sort(line.begin(), line.end());
    for(int i=0; i<quer.size(); i++) {
        while(p < line.size() && line[p].h <= quer[i].h) {
            update(1, 1, 2*n, line[p].x, line[p].y, 1);
            p++;
        }
        if(quer[i].t) {
            ans1[quer[i].id] = query(1, 1, 2*n, quer[i].x);
        } else {
            ans2[quer[i].id] = query(1, 1, 2*n, quer[i].x);
        }
    }
    for(int i=1; i<=ce; i++) {
        ans += ans1[i] - ans2[i];
    }
    printf("%d\n", ans - cnt + n);
    return 0;
}

Description

无限大正方形网格里有n个黑色的顶点,所有其他顶点都是白色的(网格的顶点即坐标为整数的点,又称整点)。每秒钟,所有内部白点同时变黑,直到不存在内部白点为止。你的任务是统计最后网格中的黑点个数。 内部白点的定义:一个白色的整点P(x,y)是内部白点当且仅当P在水平线的左边和右边各至少有一个黑点(即存在x1 < x < x2使得(x1,y)和(x2,y)都是黑点),且在竖直线的上边和下边各至少有一个黑点(即存在y1 < y < y2使得(x,y1)和(x,y2)都是黑点)。

Input

输入第一行包含一个整数n,即初始黑点个数。以下n行每行包含两个整数(x,y),即一个黑点的坐标。没有两个黑点的坐标相同,坐标的绝对值均不超过109。

Output

输出仅一行,包含黑点的最终数目。如果变色过程永不终止,输出-1。

Sample Input

4
0 2
2 0
-2 0
0 -2

Sample Output

5

数据范围

36%的数据满足:n < = 500

64%的数据满足:n < = 30000

100%的数据满足:n < = 100000