LibreOJ 3054 「HNOI2019」鱼

偷懒用了 zhoutb2333 的简单做法(
很好写啊(

首先有一个结论:平面上 \(n\) 个不同点组成的等腰三角形的个数是 \(O(n^{2.136})\) 级别的。
然后就可以用这个结论搞事情了(

容易发现的是鱼身由三个等腰三角形构成。
首先枚举 \(A\),枚举 \(B,C\),计算每对 \(B,C\) 左右两边各有多少个 \(A\)
然后枚举 \(D\),枚举 \(B,C\),就可以得到 \(AD\) 所在直线和对应的 \(A\) 的个数。
随便取一个 \(A\) 算极角(代码实现里取的是 \(\overrightarrow{DB} + \overrightarrow{DC}\) 的终点),然后对极角排序。
然后考虑枚举 \(E,F\),容易发现合法的极角也是一个区间。
二分一下就可以算答案了。

代码:

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <cmath>
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
const int N = 1e3;
const double pi = acos(-1);
const double eps = 1e-13;
int n;
struct point
{
long long x,y,dis;
int id;
inline point(long long a = 0,long long b = 0,int c = 0)
{
x = a,y = b,id = c;
}
inline point operator+(const point &o) const
{
return point(x + o.x,y + o.y);
}
inline point operator-(const point &o) const
{
return point(x - o.x,y - o.y);
}
inline point operator*(const int &v) const
{
return point(x * v,y * v);
}
inline long long operator*(const point &o) const
{
return x * o.y - y * o.x;
}
inline bool operator<(const point &o) const
{
return dis < o.dis;
}
inline double angle() const
{
return atan2(y,x);
}
} a[N + 5],t[N + 5];
inline long long dis(const point &a,const point &b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int cnt[N + 5][N + 5][2];
pair<double,int> s[N * N + 5];
int tot;
long long ans;
inline long long calc(const double &L,const double &R)
{
return (upper_bound(s + 1,s + tot + 1,make_pair(R,0x3f3f3f3f)) - 1)->second - (lower_bound(s + 1,s + tot + 1,make_pair(L,-0x3f3f3f3f)) - 1)->second;
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%lld%lld",&a[i].x,&a[i].y),a[i].id = i,t[i] = a[i];
for(register int i = 1;i <= n;++i)
{
for(register int j = 1;j <= n;++j)
t[j].dis = dis(t[j],a[i]);
sort(t + 1,t + n + 1);
for(register int l = 1,r;l <= n;l = r + 1)
{
for(r = l;r < n && dis(t[r + 1],a[i]) == dis(t[l],a[i]);++r);
for(register int j = l;j <= r;++j)
for(register int k = j + 1;k <= r;++k)
{
long long crs = (t[k] - t[j]) * (a[i] - t[j]);
if(crs)
++cnt[t[j].id][t[k].id][crs > 0],++cnt[t[k].id][t[j].id][crs < 0];
}
}
}
for(register int i = 1;i <= n;++i)
{
for(register int j = 1;j <= n;++j)
t[j].dis = dis(t[j],a[i]);
sort(t + 1,t + n + 1),tot = 0;
for(register int l = 1,r;l <= n;l = r + 1)
{
for(r = l;r < n && dis(t[r + 1],a[i]) == dis(t[l],a[i]);++r);
for(register int j = l;j <= r;++j)
for(register int k = j + 1;k <= r;++k)
{
long long crs = (t[k] - t[j]) * (a[i] - t[j]);
if(crs)
s[++tot] = make_pair((t[j] + t[k] - a[i] * 2).angle(),cnt[t[j].id][t[k].id][crs < 0]);
}
}
sort(s + 1,s + tot + 1);
for(register int i = 1;i <= tot;++i)
s[i].second += s[i - 1].second;
for(register int l = 1,r;l <= n;l = r + 1)
{
for(r = l;r < n && dis(t[r + 1],a[i]) == dis(t[l],a[i]);++r);
for(register int j = l;j <= r;++j)
for(register int k = j + 1;k <= r;++k)
{
long long crs = (t[k] - t[j]) * (a[i] - t[j]);
if(crs)
{
int x = j,y = k;
(t[y] - a[i]) * (t[x] - a[i]) > 0 && (swap(x,y),1);
double L = (t[y] - a[i]).angle() + pi / 2,R = (t[x] - a[i]).angle() + pi * 3 / 2;
L > pi && (L -= 2 * pi),R > pi && (R -= 2 * pi);
if(L < R)
ans += calc(L + eps,R - eps);
else
ans += calc(L + eps,pi) + calc(-pi,R - eps);
}
}
}
}
ans <<= 2;
printf("%lld\n",ans);
}