[数学][计算几何][极角排序][递推] UVA 11529 Strange Tax Calculation

题目链接 https://cn.vjudge.net/problem/UVA-11529

（复习期末期间日常的小题
想到了考虑每个点被多少个三角形包围，但是没想到怎么算。。。主要还是计算几何太萎le，完全没有想到可以极角排序处理emmm。

具体的就是，考虑每一个点被多少个三角形包含，但是直接考虑也不好计算，可以考虑反向计算出不被多少个三角形包含，这个计算就要用到极角排序了。。。循环遍历每个点，在每个xi点，都对所有的其他点（姑且称为角点吧）相对于这个xi点的极角做一个排序，然后利用三角形的性质，选一个方向（顺时针或者逆时针都行），依次考虑“以每个角点为最小极角与之角度差小于pi的最大角度点之间有多少个点“，可能难以理解，画个图就好了，算出来点的数量p（p包含最大的那个点）之后C(p,2)就是“包含当前最小角点的所有的不覆盖xi点的三角形数量”，依次累加就好了。。。

另外，画个图就会发现，还需要考虑圆周转一圈的情况，所以要把排序后的极角数组复制一遍，而且复制出来的这个数组每个元素还要加2pi！（这个自己试试就知道了）

然后就是找最大点的步骤要小心，很容易写错。。莫名其妙，也可能是我最近复习微机原理复习傻了。

 

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn=1205;
const int mod =1e9+7;
const int INF=0X3f3f3f3f;
const double pi=3.14159265358979323846;

int x[maxn],y[maxn],N;
double alg[maxn<<1];
bool cmp(int a,int b)
{
    return alg[a]<alg[b];
}
void asort(int k)
{
    for (int i=1,j=1;i<=N;i++)if(i!=k)
    {
        id[j]=i;
        alg[j]=atan2(y[i]-y[k],x[i]-x[k]);
        j++;
    }
    sort(alg+1,alg+N);
    for (int i=1;i<=N-1;i++)
        alg[i+N-1]=alg[i]+2*pi;
}

LL C3(LL a)
{
    if (a<3)
        return 0;
    else
        return a*(a-1)*(a-2)/6;
}

int main()
{
    int cs=0;
    while(~scanf("%d",&N)&&N)
    {
        cs++;
        for (int i=1;i<=N;i++)
            scanf("%d%d",&x[i],&y[i]);
        LL ans=0,res,tmp=0,pos;
        for (int i=1;i<=N;i++)
        {
            pos=1,res=1,tmp=0;
            asort(i);
            for (int j=1;j<=N-1;j++)
            {
                for(;alg[pos+1]-alg[j]<=pi;pos++,res++);
                tmp+=(res>=3?(res-1)*(res-2)/2:0);
                res--;
            }
            ans+=C3(N-1)-tmp;
        }
        if(N<3)
            printf("City %d: 0\n");
        else
            printf("City %d: %.2f\n",cs,(1.0*ans)/C3(N));
    }
    return 0;
}