3346. 皇后问题

单点时限: 2.0 sec

内存限制: 256 MB

八皇后问题是一个以国际象棋为背景的问题:如何能够在 $8 \times 8$ 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。

八皇后问题可以推广为更一般的 $n$ 皇后摆放问题:这时棋盘的大小变为 $n \times n$,而皇后个数也变成 $n$。

现在给你 $n$ 个皇后的位置座标,问总共有多少对皇后互相冲突。

输入格式

第一行一个整数 $n$,表示有 $n$ 个皇后。

接下来 $n$ 行,每行两个整数 $x,y$ $(1 \leq x,y \leq n)$,中间用空格分开,表示 $n$ 个皇后的坐标。

数据保证不会有两个皇后在同一个地方。

数据规模约定:

  • 对于 $60\%$ 的数据,$1 \leq n \leq 100$。
  • 对于 $100\%$ 的数据,$1 \leq n \leq 10^5$。

输出格式

输出一个整数,表示有多少对皇后互相冲突。

样例

Input
3
1 1
1 2
1 3
Output
3
Input
2
1 1
2 2
Output
1
Input
4
1 3
2 1
3 4
4 2
Output
0

819 人解决,1086 人已尝试。

1243 份提交通过,共有 6625 份提交。

2.0 EMB 奖励。

创建: 7 年,1 月前.

修改: 7 年前.

最后提交: 1 周,6 天前.

来源: 2017 直升研究生机试

题目标签