2 shunfurh 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
caozhy   Ds   Rxr 2017.01.16 23:37
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
poj3109 Inner Vertices(树状数组)
题目大意: 一个无限大的棋盘上有无数个点,这些点有黑有白,下面进行一步操作,如果有一个点,上下左右各有点,则将这个点涂成黑色。最后计算这个棋盘上黑点的数量。 思路: 这题算是我做得比较满意的一道题,也是在没有借助外界帮助的情况下,比我预期的更短的时间内A了出来(虽然贡献了两次WA)。 第一步,坐标离散化!首先,这题的棋盘的坐标的绝对值能够达到10^9这个数量级,然而点的数量却只有10^5个
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 题解
题意 给你一个无限大的白色点网格,给出n个黑点的坐标,如果一个白点上下左右都有黑点(不一定相邻),它就会变成黑点,求图上最终一共有多少个黑点。(原题意有无限多输出-1,但是想想就知道不可能) 其中n&amp;lt;=10^5 坐标绝对值&amp;lt;=10^9 分析 首先,离散化是肯定的,不然10^9处理起来不方便。 然后就可以用到扫描线法,按坐标x从小到大,x相同y从小到大排序,然后对于x值相同...
POJ 3109 Inner Vertices 树状数组
讲点无关的,发现之前BIT专题时我居然会二维的BIT……另外还水过了一道扫描线,那题目数据太小 ╮(╯-╰)╭ 这道题大概前天刷挑战的时候刷到的吧,当时粗略看了下题目,没太懂题意,这个BIT能做? 今天特地给自己定了目标这道题一定要写出来,认真的想了想 --------以上废话---------------- 关键点,绝对不可能不stop, 并且产生的点都是由最初的点产生而
poj3109 Inner Vertices 扫描线+树状数组
http://poj.org/problem?id=3109 无限大的平面上有n个黑整点,剩下的整点都是白的,如果一个白整点四周都有黑点,那么它就会变成黑点,求最后有多少个黑点。 首先白点的变化不会发生连锁反应,意味着这个变化过程一定能够终止。 变化的白点肯定是横向线段与纵向线段的交点,所以只需要找出交点的个数即可。 先离散化再找出所有的横向与纵向线段,然后扫描线+树状数组
POJ 3109 Inner Vertices(线段树)
题目链接:点击打开链接 思路: 题目可以转化成这样的问题: 有多少个白点的上下左右都有黑点, 答案是这样的白点个数 + n 怎么求符合要求的白点个数呢? 按照常见思路, 我们先对黑点进行排序, 先按x再按y将其分层。  然后我们处理到了第i列, 符合要求的白点一定在相邻的上下两个黑点之间, 我们假设此时相邻两个黑点的y坐标是L和R, 那么我们要求区间[L+1, R-1]里有多少个白点的左右
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