P1715 [USACO16DEC]Lots of Triangles好多三角形

题目描述

农民约翰希望通过卖出他拥有的一部分土地来增加收入。他在这片土地上种了\(N\)棵树(\(3\le N\le 300\))，每棵树都可以用一个二维网格图上的一个坐标来表示，没有三棵树是共线的。约翰想以3棵树做顶点围成三角形来分割地，以确定地的大小和形状，基于约翰所有树可能组成的三树组合，当然有\(L=\binom{N}{3}\)种可能考虑分割贩卖的土地切块。

一块分出的三角形土地有价值\(v\)，\(v\)的大小决定于土地上树的数量，树的数量=土地价值=\(v\)（顶点上的树不算，网格图边界不种树）。当\(v=0,1...N-3\)时，请帮约翰求出有多少三角形地\(L\)拥有价值\(v\)。

输入输出格式

输入格式：

输入的第一行为树的棵数\(N\)。

接下来的\(N\)行分别为不同树在二维网格图上的坐标；它们都是介于0和1000000之间的的整数；行和列数间用空格隔开。

输出格式：

输出\(N-2\)行，其中第\(i\)行是价值\(v\)等于\(i-1\)的土地块数量。

---

听说这个题普及组做的会比NOI的选手快

发现\(C_n^3\)可枚举，考虑枚举每一个三元组然后\(O(1)\)查询。

我们可以预处理出每条线段下端的点的个数，然后查询的时候容斥原理就行了

注意细节。

---

Code:

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=302;

pair <double,double > dx[N];

int n,ans[N],cnt[N][N],f[N];

bool check(int i,int j,int id)

{

    if((dx[id].second-dx[i].second)*(dx[j].first-dx[id].first)<(dx[j].second-dx[id].second)*(dx[id].first-dx[i].first))

        return true;

    return false;

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        scanf("%lf%lf",&dx[i].first,&dx[i].second);

    sort(dx+1,dx+1+n);

    for(int i=1;i<=n;i++)

        for(int j=i+1;j<=n;j++)

        {

            for(int l=i+1;l<=n;l++)

                if(dx[l].first>dx[i].first&&dx[l].first<dx[j].first&&check(i,j,l))

                    cnt[i][j]++;

        }

    for(int i=1;i<=n;i++)

        if(dx[i].first==dx[i-1].first)

            f[i]=f[i-1]+(dx[i].second==dx[i-1].second?0:1);

    for(int i=1;i<=n;i++)

        for(int j=i+1;j<=n;j++)

            for(int l=j+1;l<=n;l++)

            {

                if(check(i,l,j))//在下面

                {

                    if(dx[i].first==dx[j].first||dx[l].first==dx[j].first)

                        ans[cnt[i][l]-cnt[i][j]-cnt[j][l]]++;

                    else

                        ans[cnt[i][l]-cnt[i][j]-cnt[j][l]-1-f[j]]++;

                }

                else

                {

                    if(dx[i].first==dx[j].first||dx[l].first==dx[j].first)

                        ans[cnt[i][j]+cnt[j][l]-cnt[i][l]]++;

                    else

                        ans[cnt[i][j]+f[j]+cnt[j][l]-cnt[i][l]]++;

                }

            }

    for(int i=0;i<=n-3;i++)

        printf("%d\n",ans[i]);

    return 0;

}

---

2018.7.19