[BZOJ 1913] signaling 信号覆盖

Link:https://www.lydsy.com/JudgeOnline/problem.php?id=1913

TIP：（注意，这题只能输出6位才能过，7位都不行wtf？）

Algorithm:

此题要从四边形的角度去考虑

对于原图中能形成的任意一个四边形：

1、如为凸四边形，明显只有对角和大于180的那两个角形成的三角形的外接圆能包含第4个点

因此每个凸四边形对答案的贡献为2

2、如为凹四边形，对答案的贡献只有1：被其他三个角形成的三角形包含的点

于是最终结果为：

$\frac{num_{凹四边形}+2num_{凸四边形}}{C_n^3(总方案数)}+3$

由于凹四边形明显比凸四边形更好求：

$\frac{num_{凹四边形}+2(C_n^4-num_{凹四边形})}{C_n^3(总方案数)}+3$

在求凹四边形时，对于每一个点，我们只要求出其被几个三角形包含即可

但反向求解明显更方便：求多少个三角形不包含x

其他点以x为原点极角排序，对于每个点计算其ANG~ANG+PI间有多少个点，再统计能生成多少个三角形

Code：

#include <bits/stdc++.h>

using namespace std;

typedef complex<double> point;

typedef long long ll;

const int MAXN=5e3;

const double PI=3.1415926535897384626;

int n;

point dat[MAXN];

double ang[MAXN];

ll res=;

double C(double a,double b)

{

    double ret=;

    for(int i=;i<=b;i++)

        ret=ret*(a-i+)/i;

    return ret;

}

void cal(int pos)

{

    int len=;

    for(int i=;i<=n;i++) //转为极坐标系

        if(i!=pos) ang[++len]=atan2((dat[i]-dat[pos]).real(),(dat[i]-dat[pos]).imag());

    sort(ang+,ang+len+);

    ll llen=len,temp=;

    for(int i=;i<=llen;i++)  //首尾相接序列的基本操作

        ang[++len]=ang[i]+*PI;

    int cur=;

    for(int i=;i<=llen;i++)

    {

        while(cur<=len && ang[cur]<ang[i]+PI) cur++; //维护单调性

        if(cur-i->=) temp+=C(cur-i-,);

    }

    res+=C(n-,)-temp;

}

int main()

{

    cout.setf(ios::fixed);

    cout.precision();

    cin >> n;

    for(int i=;i<=n;i++) cin >> dat[i].real() >> dat[i].imag();

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

    cout << (res+(C(n,)-res)*)/C(n,)+3.0;

    return ;

}

1、求解凹四边形个数：

反向求解，利用极角排序对每个点求出不包含其的三角形的个数

2、对极坐标系的处理

由于序列是首尾相接的，要将原数组的数+2PI后扩充为原来的两倍，方便处理

3、对于包含类问题，可以将包含体和被包含点集体考虑

考虑它们看作一个整体时的性质

巴特西

[BZOJ 1913] signaling 信号覆盖

最新文章

热门文章