shunfurh 于 2017.01.11 12:03 提问

Inner Vertices

Description

There is an infinite square grid. Some vertices of the grid are black and other vertices are white.

A vertex V is called inner if it is both vertical-inner and horizontal-inner. A vertex V is called horizontal-inner if there are two such black vertices in the same row that V is located between them. A vertex V is called vertical-inner if there are two such black vertices in the same column that V is located between them.

On each step all white inner vertices became black while the other vertices preserve their colors. The process stops when all the inner vertices are black.

Write a program that calculates a number of black vertices after the process stops.

Input

The first line of the input file contains one integer number n (0 ≤ n ≤ 100 000) — number of black vertices at the beginning.

The following n lines contain two integer numbers each — the coordinates of different black vertices. The coordinates do not exceed 109 by their absolute values.

Output

Output the number of black vertices when the process stops. If the process does not stop, output -1.

Sample Input

4
0 2
2 0
-2 0
0 -2
Sample Output

5

1个回答

caozhy      2017.01.16 23:37

poj3109 Inner Vertices(树状数组)

poj 3109 Inner Vertices
#include #include #include using namespace std; #define N 200000 int n,hash[N],ans[N]; struct node { int x,y; }data[N]; int t[N]; void add(int i,int x) { while(i<=n) { ans[i]+=x; i+=i&-i; } }
【数据结构】 POJ3109 Inner Vertices 题解

POJ 3109 Inner Vertices 树状数组

poj3109 Inner Vertices 扫描线+树状数组
http://poj.org/problem?id=3109 无限大的平面上有n个黑整点，剩下的整点都是白的，如果一个白整点四周都有黑点，那么它就会变成黑点，求最后有多少个黑点。 首先白点的变化不会发生连锁反应，意味着这个变化过程一定能够终止。 变化的白点肯定是横向线段与纵向线段的交点，所以只需要找出交点的个数即可。 先离散化再找出所有的横向与纵向线段，然后扫描线+树状数组
POJ 3109 Inner Vertices（线段树）

poj 3109 Inner Vertices(树状数组）
Inner Vertices Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 1692   Accepted: 446 Case Time Limit: 2000MS Description There is an infinite square grid
poj 3109 Inner Vertices 树状数组+离散化
#include #include #include using namespace std; #define MAX_N 100000+10 typedef long long ll; ll bit0[MAX_N],bit1[MAX_N]; int N,X[MAX_N],Y[MAX_N]; vector line[MAX_N]; bool visted[MAX_N]; ll sum(ll
POJ 3109 Inner Vertices 已翻译
<span title="Description ">描述 有一个无限的方格。<span title="Some vertices of the grid are black and other vertices are white. ">网格的一些顶点是黑色的，其他顶点是白色的。 如果顶点V同时是垂直内部和水平内部，则称为内部。如果在V位于它们之间的相同行中存在两个这样的黑
codeforces 246 D. Colorful Graph (set)
D. Colorful Graph You've got an undirected graph, consisting of n vertices and m edges. We will consider the graph's vertices numbered with integers from 1 to n. Each vertex of the graph has