题解 P1715 【[USACO16DEC]Lots of Triangles好多三角形】

· · 题解

本题要用到容斥原理+简单的计算几何

最重要的一步在于如下图的容斥：

其中，L,S,R分别代表三角形三条边的正下方的树的数量

可以看出，三角形中树的数量就是|L+R-S|

因此只要预处理出每条边正下方点的数量，再枚举每个三角形就可以算出答案了

以下是各种细节，对于这道题来说，看懂上面的容斥之后建议自行完成所有细节，遇到问题再来看这篇题解：

1.一个点在一条线段的正下方⇔横坐标在线段两端点之间&&该点在该线段所在直线的下方，而点在直线下方可以用两点式+点斜式判断。

以点C和线段AB为例：

直线AB解析式为y=(yA-yB)/(xA-xB)*(x-xA)+yA

过C作AB平行线y=(yA-yB)/(xA-xB)*(x-xC)+yC

比较C与AB的位置关系即比较yA-xA(yA-yB)/(xA-xB)和yC-xC(yA-yB)/(xA-xB)的大小关系

2.每条线段的正下方应该不包括端点（否则边界会重合），并单独计算有点在公共端点下方的情况（否则边界会遗漏），然而若三角形有一边和y轴平行则不应计算有点在公共端点下方的情况，否则会将三角形的一个顶点算入答案中

3.如右图所示，如果中间的点在另两个点所组成的线段的下方，中间的点会被算入，因此在预处理每条边正下方点的数量的同时也要预处理每个点和每条线段的位置关系（当然最后计算的时候再算一遍也行，毕竟是O(1)的也不用重复计算），如果中间的点在另两个点所组成的线段的下方要将答案加1

最后代码如下：

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int n,x[310],y[310],f[310][310],ans[310]; //f用来存每条边正下方点的数量，ans存答案
bool down[310][310][310]; //存每条边和每个点的位置关系

int main()
{
    int i,j,k;
    long double kkk;

    cin>>n;

    for (i=1;i<=n;++i)
    {
        cin>>x[i]>>y[i];
    }

    for (i=1;i<n;++i) //预处理每条边正下方点的数量
    {
        for (j=i+1;j<=n;++j)
        {
            if (x[i]==x[j]) //记录有点在公共端点下方的情况，并且如果出现这种情况就不用判断这条线段和其它点的位置关系了
            {
                if (y[i]<y[j])
                {
                    ++f[0][j];
                }
                else
                {
                    ++f[0][i];
                }
            }
            else
            {
                for (k=1;k<=n;++k)
                {
                    if (i!=k&&j!=k&&x[k]>min(x[i],x[j])&&x[k]<max(x[i],x[j])) //判断点和线段的位置关系
                    {
                        kkk=1.0*(y[i]-y[j])/(x[i]-x[j]);
                        if (y[i]-kkk*x[i]>y[k]-kkk*x[k])
                        {
                            ++f[i][j];
                            down[i][j][k]=true;
                        }
                    }
                }
            }
        }
    }

    for (i=1;i<=n-2;++i)
    {
        for (j=i+1;j<n;++j)
        {
            for (k=j+1;k<=n;++k)
            {
                if (x[i]<=x[j]&&x[i]>=x[k]||x[i]>=x[j]&&x[i]<=x[k]) //找出横坐标在中间的点是哪个
                {
                    if (x[i]==x[j]||x[i]==x[k]) //判断是否有边和y轴平行
                    {
                        ++ans[abs(f[i][j]+f[i][k]-f[j][k]+down[j][k][i])];
                    }
                    else
                    {
                        ++ans[abs(f[i][j]+f[i][k]+f[0][i]-f[j][k]+down[j][k][i])];
                    }
                }
                else if (x[j]<=x[i]&&x[j]>=x[k]||x[j]>=x[i]&&x[j]<=x[k])
                {
                    if (x[i]==x[j]||x[j]==x[k])
                    {
                        ++ans[abs(f[i][j]+f[j][k]-f[i][k]+down[i][k][j])];
                    }
                    else
                    {
                        ++ans[abs(f[i][j]+f[j][k]+f[0][j]-f[i][k]+down[i][k][j])];
                    }
                }
                else
                {
                    if (x[i]==x[k]||x[j]==x[k])
                    {
                        ++ans[abs(f[i][k]+f[j][k]-f[i][j]+down[i][j][k])];
                    }
                    else
                    {
                        ++ans[abs(f[i][k]+f[j][k]+f[0][k]-f[i][j]+down[i][j][k])];
                    }
                }
            }
        }
    }

    for (i=0;i<n-2;++i)
    {
        cout<<ans[i]<<endl;
    } 

    return 0;
}