[数学][计算几何][极角排序][递推] 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;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据