# Codeforces - 1166C - A Tale of Two Lands

## 地址

http://codeforces.com/contest/1166/problem/C

## 原文地址

https://www.lucien.ink/archives/432

## 题目

The legend of the foundation of Vectorland talks of two integers $x$ and $y$. Centuries ago, the array king placed two markers at points $|x|$ and $|y|$ on the number line and conquered all the land in between (including the endpoints), which he declared to be Arrayland. Many years later, the vector king placed markers at points $|x - y|$ and $|x + y|$ and conquered all the land in between (including the endpoints), which he declared to be Vectorland. He did so in such a way that the land of Arrayland was completely inside (including the endpoints) the land of Vectorland.

Here $|z|$ denotes the absolute value of $z$.

Now, Jose is stuck on a question of his history exam: "What are the values of $x$ and $y$?" Jose doesn't know the answer, but he believes he has narrowed the possible answers down to $n$ integers $a_1, a_2, \dots, a_n$. Now, he wants to know the number of unordered pairs formed by two different elements from these $n$ integers such that the legend could be true if $x$ and $y$ were equal to these two values. Note that it is possible that Jose is wrong, and that no pairs could possibly make the legend true.

## 题解

1. $0 < x,y$

$$y - x \leq x \leq y \leq x + y \Rightarrow x \leq y \leq 2x$$

1. $x < 0$, $y > 0$

$$x + y \leq -x \leq y \leq y - x \Rightarrow -x \leq y \leq -2x$$

1. $x > 0$, $y < 0$

$$-y - x \leq x \leq -y \leq x - y \Rightarrow x \leq -y \leq 2x$$

1. $0 > x, y$

$$x - y \leq -x \leq -y \leq -x - y \\ \Rightarrow 2x \leq y \leq x \\ \Rightarrow |x| \leq |y| \leq 2|x|$$

1. 只有当 $x$ 和 $y$ 同时为 $0$ 时才满足不等式

### 代码

https://pasteme.cn/8175

#include <bits/stdc++.h>
long long ans, n;
std::vector<int> vec;
std::map<int, int> cnt;
int main() {
scanf("%d", &n);
for (int i = 0, buf; i < n; i++) {
scanf("%d", &buf);
vec.push_back(abs(buf));
cnt[abs(buf)]++;
}
std::sort(vec.begin(), vec.end());
for (auto each : vec) {
auto l = std::lower_bound(vec.begin(), vec.end(), each);
auto r = std::upper_bound(vec.begin(), vec.end(), each * 2);
ans += r - l;
}
for (auto pair : cnt) ans -= pair.second * pair.second - pair.second * (pair.second - 1) / 2;
printf("%lld\n", ans);
return 0;
}