前一段时间做的一道题目，感觉思维很精妙，发上来与大家共享

题意简述：
n个白点和n个黑点，如果异色点曼哈顿距离不超过C则黑向白连边，否则白向黑连边，同色点的连边方向自定，问最少和最多有多少个异色三度环。
n≤100000。

关键字：线段树，三角形计数

算法描述：
将每个点的控制范围旋转45°，则对于每个点，来自异色点的入度可以通过线段树维护扫描线求矩形内的点数求出。对于两个同色点，从入度少的连向入度多的点可以使得三角形最少（例如对于两个白点ab，在a控制范围内的黑点全部向a连边，且b向这些点连边，则如果从a向b连边，这些点就会被加入答案），反之则为最大值，这样我们就可以求出两种答案所对应方案下每个点的入度。
接下来就是统计答案的问题了，由于三度环不好考虑，所以我们考虑其补集——同向三角形，即存在一个顶点使得在这个三角形中有两条边作为该点的入度。这样的三角形可以靠枚举一个点，求在入度中任选两条边的组合数得到。注意：无论是求总数还是求同向三角形，都要减去同色三角形的部分。

分析&总结：
带有组合数的题目要想清楚了将公式写下，敲完代码还要认真核对一遍！
本题容易想到直接去扣除两个矩形相交部分的点求解，但是这样很麻烦。用三角形计数的方式重新计算答案可以很好地解决这个问题。

My Code：

/*
Title: Triangle
Author: LTL
*/

#include <iostream>
#include <memory.h>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>

#define InputFileName        "XXXXXXX"
#define OutputFileName        "Data.out"

using namespace std;

const int MaxN = 1100000, oo = 1000000000, QLen = MaxN, MaxM = 20;

int n, m, Queue[QLen+1], QHead, QTail, a[MaxM], Path[MaxN], f[MaxN], Ans[MaxN], Total;
bool Flag[MaxN];

void Init()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        cin >> a[i];
    sort(a+1, a+m+1);
}

void SPFA()
{
    memset(Path, 127, sizeof(f[0])*n);
    memset(Flag, 0, sizeof(Flag[0])*n);
    QHead = QTail = 0;
    Queue[++QTail] = 0;
    for (int t, i, v; QHead < QTail;)
        for (t = Queue[++QHead], i = 1; i <= m; ++i)
            if (! Flag[v = (t*10+a[i]) % n] && (Path[t] < oo || a[i]))
            {
                Path[v] = t;
                f[v] = a[i];
                Flag[Queue[++QTail] = v] = 1;
            }
}

void Print()
{
    Total = 0;
    int i;
    for (i = 0; Path[i] && Path[i] < oo; i = Path[i])
        Ans[++Total] = f[i];
    if (Path[i] < oo)
        Ans[++Total] = f[i];
    else
        printf("0");
    for (; Total; --Total)
        printf("%d", Ans[Total]);
    printf("\n");
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen(InputFileName, "r", stdin);
    freopen(OutputFileName, "w", stdout);
    #endif
    int TestCase;
    for (cin >> TestCase; TestCase; --TestCase)
    {
        Init();
        SPFA();
        Print();
    }
    return 0;
}