题目链接：http://codeforces.com/problemset/problem/382/C
题目意思：给定一个序列，问是否可以通过只插入一个数来使得整个序列成为等差数列，求出总共有多少可能的情况，并输出这些数。
n = 1 、 n = 2 和 整个序列是常数列 的情况比较容易判断。不过要注意n = 2的时候，也需要判断两个数之间是否也可以通过插入一个数来构成等差数列。
关键是讨论n>=3的情况。预处理：把整个输入序列从小到大排序。之后，得到公差是第一要务！如果可以从中插入一个数（这时一定不是两端，也就是说这两种情况是互斥的），那么两个相邻的数之差 = 公差的次数会是最多的！只要找到这个差出现不少于2次以上，这个差就是公差。
确定公差之后，后面的情况就比较容易判断。插入该数的两个相邻数之间的差不可能等于公差，而该数是否合法，可以通过这两个相邻数中较小的一个 + 2倍公差，能否得到较大的数来判断。
如果插入的数不在中间，那么有可能是无解（输出0，插入哪个位置都不能使得序列成为等差数列）或者是从两端插入（输入的序列已经是等差数列）
还有一种情况要特别注意，当序列只有3个数的时候，并且可以从中插入一个数成为等差数列的情况。此时公差取较小的那个差，因为较大的差之间比较小的差能插入该数的可能性更大。例如序列：1 3 4，我们会取1作为公差，而不是2，此时可在1和3之间插入2来构成等差数列。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std; const int maxn = 1e5 + ;
int a[maxn]; int main()
{
int i, cnt, n, d, ans, td, td1, c1, c2;
while (scanf("%d", &n) != EOF)
{
for (i = ; i <= n; i++)
scanf("%d", &a[i]);
sort(a+, a+n+);
d = a[]-a[];
if (n == ) // 可以插入无限个数，只要等于a[1]就行
printf("-1\n");
else if (a[] == a[n] && n >= ) // 常数列
printf("1\n%d\n", a[]);
else if (n == )
{
if ((a[] + a[]) % ) // 判断相邻数之间是否也可以插入
printf("2\n%d %d\n", a[]-d, a[]+d);
else
printf("3\n%d %d %d\n", a[]-d, (a[]+a[])/, a[]+d);
}
else
{
if (n >= )
{
c2 = c1 = ;
td1 = a[]-a[];
if (td1 != d)
{
for (i = ; i <= n; i++)
{
int td = a[i] - a[i-];
// 出现次数>=2的差即为整个序列的公差 if (td == td1)
c2++;
else
c1++;
if (c1 >= || c2 >= )
break;
}
}
if (c2 >= c1 && n >= && d > td1) // 最终确定公差
d = td1;
}
cnt = ;
for (i = ; i <= n; i++)
{
td = a[i] - a[i-];
if (d != td)
{
cnt++;
if ((a[i-]+a[i]) % || a[i-]+*d != a[i])
{
cnt++;
break;
}
else
ans = a[i-] + d;
}
}
if (!cnt)
printf("2\n%d %d\n", a[]-d, a[n]+d);
else if (cnt == )
printf("1\n%d\n", ans);
else
printf("0\n");
}
}
return ;
}