几何

本文最后更新于：星期四, 二月 3日 2022, 9:15 晚上

2018-2019 ACM-ICPC, Asia Shenyang Regional Contest

L. Machining Disc Rotors

题意：给定一个圆，被nn个圆切割，求剩下部分最远距离

思路：最远距离一定是两个交点或者原本圆的直径(水)

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
using ll = long long;
using db = double;

const int N = 110;
const db eps = 1e-11;

int sgn(db x) {
    if (fabs(x) < eps) return 0;
    else return x > 0 ? 1 : -1;
}

struct Point {
    db x, y;

    Point() {}
    
    Point(db _x, db _y) {
        x = _x, y = _y;
    }
    
    db len() {
        return hypot(x, y);
    }
    
    db distance(Point &other) {
        return hypot(x - other.x, y - other.y);
    }
    
    Point operator+(const Point &other) const {
        return {x + other.x, y + other.y};
    }
    
    Point operator-(const Point &other) const {
        return {x - other.x, y - other.y};
    }
    
    Point trunc(db r) {
        db l = len();
        if (!sgn(l)) {
            return *this;
        }
        r /= l;
        return {x * r, y * r};
    }
    
    Point rotright() {
        return {-y, x};
    }
    
    Point rotleft() {
        return {y, -x};
    }
    
    Point change() {
        return {-x, -y};
    }

};

struct Circle {
    Point p;
    db r;

    void input() {
        scanf("%lf %lf %lf", &p.x, &p.y, &r);
    }
    
    Circle() {}
    
    Circle(Point _p, db _r) {
        p = _p, r = _r;
    }
    
    Circle(db _x, db _y, db _r) {
        p = Point(_x, _y);
        r = _r;
    }
    
    int relationcicle(Circle v) {
        db d = p.distance(v.p);
        if (sgn(d - r - v.r) > 0) return 5;
        if (sgn(d - r - v.r) == 0) return 4;
        db l = fabs(r - v.r);
        if (sgn(d - r - v.r) < 0 && sgn(d - l) > 0) return 3;
        if (sgn(d - l) == 0) return 2;
        else return 1;
    }
    
    int pointcrosscircle(Circle v, Point &p1, Point &p2) {
        int rel = relationcicle(v);
        if (rel == 1 || rel == 5) return 0;
        db d = p.distance(v.p);
        db l = (d * d + r * r - v.r * v.r) / (2 * d);
        db h = sqrt(r * r - l * l);
        Point tmp = p + (v.p - p).trunc(l);
        p1 = tmp + ((v.p - p).rotleft().trunc(h));
        p2 = tmp + ((v.p - p).rotright().trunc(h));
        if (rel == 2 || rel == 4) {
            return 1;
        }
        return 2;
    }

} o, a[N];

int n;
db r;
vector<Point> vec;

void gao(Circle tmp) {
    Point p[2];
    int res = o.pointcrosscircle(tmp, p[0], p[1]);
    for (int i = 0; i < res; ++i) {
        vec.push_back(p[i]);
    }
}

bool check() {
    for (auto p : vec) {
        p = p.change();
        bool F = true;
        for (int i = 1; i <= n; ++i) {
            db dis = p.distance(a[i].p);
            if (sgn(dis - a[i].r) < 0) {
                F = false;
                break;
            }
        }
        if (F) {
            return true;
        }
    }
    return false;
}

void RUN() {
    vec.clear();
    scanf("%d %lf", &n, &r);
    o = Circle(0.0, 0.0, r);
    for (int i = 1; i <= n; ++i) {
        a[i].input();
        gao(a[i]);
    }
    db res = 0;
    for (int i = 0, len = vec.size(); i < len; ++i) {
        for (int j = i + 1; j < len; ++j) {
            res = max(res, vec[i].distance(vec[j]));
        }
    }
    if (check()) {
        res = 2 * r;
    }
    printf("%.15f\n", res);
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif

//    ios::sync_with_stdio(false);
//    cin.tie(nullptr), cout.tie(nullptr);

    int _T;
    scanf("%d", &_T);
    for (int cas = 1; cas <= _T; ++cas) {
        printf("Case #%d: ", cas);
        RUN();
    }

#ifdef LOCAL_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

2018 German Collegiate Programming Contest (GCPC 18)

B. Battle Royale

题意：求两个点不穿过圆的最短距离

思路：高中数学水一水

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

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
using ll = long long;
using db = double;

const db eps = 1e-9;

int sgn(db x) {
    if (fabs(x) < eps) return false;
    else return x > 0 ? 1 : -1;
}

struct Point {
    db x, y;

    Point() {}
    
    Point(db _x, db _y) {
        x = _x, y = _y;
    }
    
    db operator^(const Point &other) const {
        return x * other.y - y * other.x;
    }
    
    db operator*(const Point &other) const {
        return x * other.x + y * other.y;
    }
    
    Point operator-(const Point &other) const {
        return {x - other.x, y - other.y};
    }
    
    db distance(Point p) {
        return hypot(x - p.x, y - p.y);
    }
} A, B, o;

struct Line {
    Point s, e;

    Line() {}
    
    db length() {
        return s.distance(e);
    }
    
    Line(Point _s, Point _e) {
        s = _s, e = _e;
    }
    
    db dispointtoline(Point p) {
        return fabs((p - s) ^ (e - s)) / length();
    }
    
    db dispointtoseg(Point p) {
        if (sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0) {
            return min(p.distance(s), p.distance(e));
        } else {
            return dispointtoline(p);
        }
    }
} l;

db r;

db f(db a, db b, db c) {
    return acos((a * a + b * b - c * c) / (2.0 * a * b));
}

void RUN() {
    scanf("%lf %lf", &A.x, &A.y);
    scanf("%lf %lf", &B.x, &B.y);
    scanf("%lf %lf %lf", &o.x, &o.y, &r);
    scanf("%lf %lf %lf", &o.x, &o.y, &r);
    l = Line(A, B);
    db dis = l.dispointtoseg(o);
    db res = 0;
    if (sgn(dis - r) >= 0) {
        res = A.distance(B);
    } else {
        dis = A.distance(B);
        db dis1 = A.distance(o);
        db c1 = sqrt(dis1 * dis1 - r * r);
        res += c1;
        db dis2 = B.distance(o);
        db c2 = sqrt(dis2 * dis2 - r * r);
        res += c2;
        db arc = f(dis1, dis2, dis);
        db arc1 = f(dis1, r, c1);
        db arc2 = f(dis2, r, c2);
        db arc3 = arc - arc1 - arc2;
        res += r * arc3;
    }
    printf("%.10f\n", res);
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif

    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    RUN();

#ifdef LOCAL_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

ACM-ICPC Asia Beijing Regional Contest 2018 Reproduction

J. Rikka with Triangles

题意：给出nn个点，求所有锐角三角形的面积和。n≤2000n\leq2000

思路：枚举每个点进行极角排序，双指针枚举计算所有三角形面积rea1rea1以及直角三角形和钝角三角形面积和res2res2那么答案为res1−2×res23\frac{res1 - 2 \times res2}{3}

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

#include <bits/stdc++.h>

using namespace std;

#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)

void err() { cout << "\033[39;0m" << endl; }

template<class T, class... Ts>
void err(const T &arg, const Ts &... args) {
    cout << arg << ' ';
    err(args...);
}


#define endl "\n"
using ll = long long;
using db = double;
using LL = __int128;

const int N = 5e3 + 10;
const ll mod = 998244353;

template<class T>
inline bool read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return false;
    while (c != '-' && !isdigit(c)) c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), isdigit(c)) ret = ret * 10 + (c - '0');
    ret *= sgn;
    return true;
}

ll qpow(ll x, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) {
            res = res * x % mod;
        }
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

int n;

struct Point {
    LL x, y;

    Point() {}
    
    Point(LL x, LL y) : x(x), y(y) {}
    
    Point operator-(const Point &other) const {
        return {x - other.x, y - other.y};
    }
    
    Point operator+(const Point &other) const {
        return {x + other.x, y + other.y};
    }
    
    LL operator^(const Point &other) const {
        return x * other.y - y * other.x;
    }
    
    bool operator<(const Point &other) const {
        if (y < 0 && other.y > 0) return true;
        if (y > 0 && other.y < 0) return false;
        if (y == 0 && other.y == 0) {
            return (x < 0 && other.x > 0);
        } else {
            return ((*this) ^ other) > 0;
        }
    }
} p[N], qrr[N];

LL sumx[N], sumy[N];

LL gao() {
    LL res1 = 0, res2 = 0;
    for (int i = 1; i <= n; ++i) {
        int cnt = 0;
        for (int j = 1; j <= n; ++j) {
            if (i == j) continue;
            qrr[++cnt] = p[j] - p[i];
        }
        sort(qrr + 1, qrr + 1 + cnt);
        for (int j = 1; j <= cnt; ++j) {
            qrr[j + cnt] = qrr[j];
        }
        sumx[0] = sumy[0] = 0;
        cnt <<= 1;
        for (int j = 1; j <= cnt; ++j) {
            sumx[j] = (sumx[j - 1] + qrr[j].x) % mod;
            sumy[j] = (sumy[j - 1] + qrr[j].y) % mod;
        }
        int q = 1, s = 1, t = 1;
        for (int j = 1; j < n; ++j) {
            q = max(q, j);
            Point _90 = Point(-qrr[j].y, qrr[j].x);
            Point _180 = Point(-qrr[j].x, -qrr[j].y);
            while (q < cnt && (qrr[q + 1] ^ qrr[j]) == 0) ++q;
            while (s < cnt && (s < q || ((qrr[s + 1] ^ _90) > 0 && (qrr[s + 1] ^ qrr[j]) <= 0))) ++s;
            while (t < cnt && (t < s || ((qrr[t + 1] ^ _180) > 0 && (qrr[t + 1] ^ _90) <= 0))) ++t;
            res1 = (res1 + (sumy[s] - sumy[q] + mod) % mod * (qrr[j].x % mod) % mod -
                    (sumx[s] - sumx[q] + mod) % mod * (qrr[j].y) % mod + mod) % mod;
            res2 = (res2 + (sumy[t] - sumy[s] + mod) % mod * (qrr[j].x % mod) % mod -
                    (sumx[t] - sumx[s] + mod) % mod * (qrr[j].y) % mod + mod) % mod;
        }
    }
    return ((res1 - res2 * 2 % mod + mod) % mod * qpow(3, mod - 2) % mod) % mod;
}

void RUN() {
    int T;
    read(T);
    while (T--) {
        read(n);
        for (int i = 1; i <= n; ++i) {
            read(p[i].x), read(p[i].y);
        }
        ll res = gao();
        printf("%lld\n", res);
    }
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif

//    ios::sync_with_stdio(false);
//    cin.tie(nullptr), cout.tie(nullptr);

    RUN();

#ifdef LOCAL_JUDGE
//    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

知识点

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！