1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include <cstdio>
#include <iomanip>
#include <cstring>
using namespace std;
struct node_type {
int l, r, child[2];
} node[300001];
struct edge {
int v, c, nxt;
} e[600001];
int n, tot, nume, id, h[300001], que[600001], dfn[300001], low[300001];
int top, sta[300001], cnt, belong[300001], pnt[300001];
long double ans;
bool vis[300001];
void add_edge(int u, int v) {
if (u == v) return;
e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
}
void build_tree(int root) {
int mid = node[root].l + node[root].r >> 1;
if (node[root].l == mid) {
node[root].child[0] = mid, add_edge(root, mid);
} else {
node[++tot].l = node[root].l, node[tot].r = mid;
node[root].child[0] = tot, add_edge(root, tot), build_tree(tot);
}
if (mid + 1 == node[root].r) {
node[root].child[1] = mid + 1, add_edge(root, mid + 1);
} else {
node[++tot].l = mid + 1, node[tot].r = node[root].r;
node[root].child[1] = tot, add_edge(root, tot), build_tree(tot);
}
}
void insert_line(int root, int l, int r, int t) {
if (node[root].l == l && node[root].r == r) {
add_edge(t, root); return;
}
int mid = node[root].l + node[root].r >> 1;
if (r <= mid) insert_line(node[root].child[0], l, r, t);
else if (l > mid) insert_line(node[root].child[1], l, r, t);
else {
insert_line(node[root].child[0], l, mid, t);
insert_line(node[root].child[1], mid + 1, r, t);
}
}
void dfs(int t) {
dfn[t] = low[t] = ++id;
sta[++top] = t, vis[t] = true;
for (int i = h[t]; i; i = e[i].nxt) {
if (!dfn[e[i].v]) dfs(e[i].v), low[t] = min(low[t], low[e[i].v]);
else if (vis[e[i].v]) low[t] = min(low[t], dfn[e[i].v]);
}
if (dfn[t] == low[t]) {
int v; ++cnt;
do belong[v = sta[top--]] = cnt, vis[v] = false; while (v != t);
}
}
int bfs(int u) {
memset(vis, false, sizeof(vis));
int s = 0, t = 0, ret = 1;
vis[que[++t] = u] = true;
while (s < t) {
int v = que[++s];
for (int i = h[v]; i; i = e[i].nxt) {
if (!vis[e[i].v]) {
vis[que[++t] = e[i].v] = true;
if (e[i].v && e[i].v <= n) ++ret;
}
}
}
return ret;
}
int main()
{
scanf("%d", &n); tot = n + 1;
for (int i = 1; i <= n; ++i) node[i].l = node[i].r = i;
node[tot].l = 1, node[tot].r = n, build_tree(tot);
for (int i = 1; i <= n; ++i) {
int l, r;
scanf("%d%d", &l, &r);
insert_line(n + 1, l, r, i);
}
for (int i = 1; i <= tot; ++i) if (!dfn[i]) dfs(i);
for (int i = 1; i <= n; ++i) {
if (!pnt[belong[i]]) pnt[belong[i]] = bfs(i);
ans += pnt[belong[i]];
}
printf("%.6llf\n", ans / n);
return 0;
}
|