游客 注册 | 登录
中文 | En

3321 - 棋子

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

给定一个无穷大的棋盘，上面有一些棋子，而在你的手里有无穷多个棋子。然后如果你看到三个棋子组成了一个两边平行于坐标轴的矩形的三个顶点，而第四个顶点上没有棋子，那么你就要在那个顶点上放一个棋子，一直到没有可以放的位置为止。

那么问题来了，你可不可以无限的放下去呢？如果不能，请输出棋盘上最后的棋子数量。

题目输入

第一行一个整数n表示有n个棋子一开始就在棋盘上。

接下来n行，每行都表示一个棋子的坐标，其中x坐标在前，y坐标在后。

<span style="font-size:10.5pt;font-family:宋体;">输入数据可能会出现开始时同一个位置放置了多个棋子的情况，这些棋子只计算为一个棋子。</span>


<br />


<span style="font-size:10.5pt;font-family:宋体;">
<p class="MsoNormal" style="text-indent:21.0pt;">
	<span style="font-family:宋体;">对于</span><span>40%</span><span style="font-family:宋体;">的数据，</span><span>n&lt;=5000</span>
</p>
<p class="MsoNormal" style="text-indent:21.0pt;">
	<span style="font-family:宋体;">对于</span><span>100%</span><span style="font-family:宋体;">的数据，</span><span>n&lt;=200000</span>
</p>
<p class="MsoNormal" style="text-indent:21.0pt;">
	X<span style="font-size:10.5pt;font-family:宋体;">和</span><span style="font-size:10.5pt;font-family:&quot;">y</span><span style="font-size:10.5pt;font-family:宋体;">都在</span><span style="font-size:10.5pt;font-family:&quot;">longint(Pascal)</span><span style="font-size:10.5pt;font-family:宋体;">和</span><span style="font-size:10.5pt;font-family:&quot;">int(C++)</span><span style="font-size:10.5pt;font-family:宋体;">的范围内</span>
</p>

题目输出

一行一个整数，如果能无限放下去，输出-1，否则输出最后的棋子数（不保证范围）

输入/输出样例

输入格式

3
0 0
0 1
1 0

输出格式

4

C++解答

/*
	author :hzoi_ztx
	title  :棋子 
	ALG    :DFS 
	CMT    :二分图思想 嗯,只能说忘了KM怎么写了 = = 
			将未访问过的点加入集合,然后模拟模拟就粗来了
			预计能过一些点吧 
	[2014 10 23]
*/

#include <cstdio>
#include <map>

#define  maxn  200010
#define  maxe  500010
#define  maxt  400010

typedef long long ll ;

struct FST{
	ll to , next ;
} e[maxe] ; ll star[maxt] = {0} , tote = 0 ;

void addEdge(ll u , ll v) {
	tote ++ ; e[tote].to = v ;
	e[tote].next = star[u] ; star[u] = tote ;
}

ll n , ans = 0 ;
ll cntx = 0 , cnty = 200000 ;
std::map<ll,ll>existx ;
std::map<ll,ll>existy ;
bool visit[maxt] = {0} ;

ll Left , Right ;

void dfs(ll s, bool left) {
	ll t , p ;
	if (left) {
		Left ++ ; ans += Right ;
	} else {
		Right ++ ; ans += Left ;
	}
	for (p=star[s],t=e[p].to;p;p=e[p].next,t=e[p].to) {
		if (!visit[t]) {
			visit[t] = true ; dfs(t , !left) ;
		}
	}
}

int main() {
//	#define READ
	#ifdef  READ
		freopen("chess.in" ,"r",stdin ) ;
		freopen("chess.out","w",stdout) ;
	#endif
	ll i , x , y ;
	scanf("%lld", &n ) ;
	existx.clear() ;
	existy.clear() ;
	for (i = 1 ; i <= n ; i ++ ) {
		scanf("%lld%lld", &x , &y ) ;
		if (existx[x]) x = existx[x] ;
		else { existx[x] = ++cntx ; x = cntx ; }
		if (existy[y]) y = existy[y] ;
		else { existy[y] = ++cnty ; y = cnty ; }
		addEdge(x , y) ; addEdge(y , x) ;
	}
	for (i = 1 ; i <= cntx ; i ++ ) {
		if (!visit[i]) {
			visit[i] = true ;
			Left = 0 ; Right = 0 ;
			dfs(i , true) ;
		}
	}
	printf("%lld\n", ans ) ;
	#ifdef  READ
		fclose(stdin ) ;
		fclose(stdout) ;
	#endif
	return 0 ;
}
请先登陆