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);
}

Gitalking ...