BZOJ1913【APIO2010】信号覆盖 <极角排序+双指针>

Problem

【APIO2010】信号覆盖

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;64\;MB}$

Description


Input

输入第一行包含一个正整数$n$，表示房子的总数。接下来有$n$行，分别表示每一个房子的位置。对于，$i=1,2,\cdots,n$第$i$个房子的坐标用一对整数$x_i$和$y_i$来表示，中间用空格隔开。

Output

输出文件包含一个实数，表示平均有多少个房子被信号所覆盖，需保证输出结果与精确值的绝对误差不超过$0.01$。

Sample Input

4
0 2
4 4
0 0
2 0

Sample Output

3.500

HINT

$40\%$的数据，$n\le100$
$70\%$的数据，$n\le500$
$100\%$的数据，$3\le n\le1500$
$100\%$的数据保证，对于$i=1,2,\cdots,n$，第$i$个房子的坐标$(x_i,y_i)$为整数且$-10^6\le x_i,y_i\le10^6$。
任何三个房子不在同一条直线上，任何四个房子不在同一个圆上。

标签：极角排序 双指针

Solution

总体思路是求出所有三元组形成的圆能多覆盖的点的总数$tot$，$ans=tot\div\binom{n}{3}+3$

对于任意四点构成的四边形，考虑任选其中任意三点形成的圆能否包括另一个点。
有两种情况：

1. 凹四边形：除凹进去的点外另外三点的外接圆可以包括凹进去的点外，其余三元组构成的圆一定不能包括第四点，故贡献为$1$。
2. 凸四边形：由于不存在共圆四边形，对角和一定一个大于$180^\circ$，一个小于$180^\circ$。只有对角和大于$180^\circ$的两个角上三点的外接圆能包括另一点，故贡献为$2$。

因此$tot=凹四边形数+2\times凸四边形数$。

接下来考虑如何求两种四边形的个数。由于$凹四边形数+凸四边形数=\binom{n}{4}$，我们只用求凹四边形个数即可。
枚举每个点，考虑其作为凹四边形凹进去的那个点又多少种情况。易知$情况数=\binom{n-1}{3}-含此点的凸多边形数$。于是需要求含此点$(p)$的凸多边形数。即枚举凸多边形上的另一个点$(q)$，看有多少点$(r)$使得$pr$和$pq$的夹角小于$180^\circ$。这个过程可以用极角排序后双指针扫一遍统计。这样$O(n^2)$计算出凹多边形数后即可得到最终答案。

Code

#include <bits/stdc++.h>
#define Pi acos(-1)
#define x first
#define y second
#define MAX_N 1500
using namespace std;
typedef double dnt;
typedef long long lnt;
typedef pair<dnt,dnt> pdd;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n; lnt c1, c2; pdd p[MAX_N+5];
lnt C(int n, int m) {
    lnt ret = 1LL;	if (n < m) return 0LL;
    for (int i = 1; i <= m; i++) ret *= 1LL*(n-i+1);
    for (int i = 1; i <= m; i++) ret /= i;
    return ret;
}
int main() {
    read(n);
    for (int i = 1; i <= n; i++)
        read(p[i].x), read(p[i].y);
    for (int i = 1, m = 0; i <= n; i++, m = 0) {
        lnt tot = 0LL; dnt a[MAX_N*2+5];
        for (int j = 1; j <= n; j++) if (i^j)
            a[++m] = atan2(p[j].y-p[i].y, p[j].x-p[i].x);
        for (int j = 1; j <= n; j++) if (a[j] < 0) a[j] += 2*Pi;
        sort(a+1, a+m+1);
        for (int j = 1; j <= m; j++) a[m+j] = a[j]+2*Pi;
        for (int u = 1, v = 1; u <= m; tot += C(v-u, 2), u++)
            while (v < (m<<1) && a[v+1]-a[u] < Pi) v++;
        c1 += C(m, 3)-tot;
    }
    c2 = C(n, 4)-c1;
    return printf("%.6lf\n", (dnt)(c1+c2*2)/(dnt)C(n, 3)+3), 0;
}