Star's Blog

1
#include <iostream>
2
#include <cstring>
3
#define x first
4
#define y second
5

6
using namespace std;
7

8
const int N = 5010;
9
typedef long long LL;
10
typedef pair<LL, LL> PLL;
11

12
PLL operator -(PLL a, PLL b) {
13
    return {a.x - b.x, a.y - b.y};
14
}
15

16
LL operator *(PLL a, PLL b) {
17
    return a.x * b.y - a.y * b.x;
18
}
19

20
LL area(PLL a, PLL b, PLL c) {
21
    return (b - a) * (c - a);
22
}
23

24
struct Line {
25
    PLL u, d;
26
} a[N];
27
int res[N];
28

29
int main() {
30
    bool first = true;
31
    int n, m, x1, y1, x2, y2;
32
    while (scanf("%d", &n), n) {
33
        memset(res, 0, sizeof(res));
34
        scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
35
        for (int i = 1; i <= n; ++i) {
36
            int u, l;
37
            scanf("%d%d", &u, &l);
38
            a[i] = {{u, y1}, {l, y2}};
39
        }
40
        a[0] = {{x1, y1}, {x1, y2}};
41
        a[n + 1] = {{x2, y1}, {x2, y2}};
42
        for (int i = 1; i <= m; ++i) {
43
            PLL p;
44
            scanf("%lld%lld", &p.x, &p.y);
45
            int l = 0, r = n;
46
            while (l < r) {
47
                int mid = l + r + 1 >> 1;
48
                if (area(p, a[mid].u, a[mid].d) > 0) l = mid;
49
                else r = mid - 1;
50
            }
51
            res[l]++;
52
        }
53
        if (first) first = false;
54
        else printf("\n");
55
        for (int i = 0; i <= n; ++i) {
56
            printf("%d: %d\n", i, res[i]);
57
        }
58
    }
59
    return 0;
60
}

1
#include <iostream>
2
#include <cmath>
3
#define x first
4
#define y second
5

6
using namespace std;
7
typedef pair<double, double> PDD;
8
const int N = 110;
9
const double eps = 1e-8;
10

11
struct Line {
12
    PDD s[2];
13
} a[N];
14

15
int dcmp(double a, double b) {
16
    if (fabs(a - b) < eps) return 0;
17
    else if (a < b) return -1;
18
    else return 1;
19
}
20

21
int sign(double a) {
22
    if (fabs(a) < eps) return 0;
23
    else if (a < 0) return -1;
24
    else return 1;
25
}
26

27
PDD operator - (PDD a, PDD b) {
28
    return {a.x - b.x, a.y - b.y};
29
}
30

31
double operator * (PDD a, PDD b) {
32
    return a.x * b.y - a.y * b.x;
33
}
34

35
double area(PDD a, PDD b, PDD c) {
36
    return (b - a) * (c - a);
37
}
38

39
void solve() {
40
    int n;
41
    scanf("%d", &n);
42
    for (int i = 1; i <= n; ++i) {
43
        scanf("%lf%lf%lf%lf", &a[i].s[0].x, &a[i].s[0].y, &a[i].s[1].x, &a[i].s[1].y);
44
    }
45
    for (int i = 1; i <= n; ++i) {
46
        for (int t1 = 0; t1 < 2; ++t1) {
47
            for (int j = 1; j <= n; ++j) {
48
                for (int t2 = 0; t2 < 2; ++t2) {
49
                    PDD s = a[i].s[t1], t = a[j].s[t2];
50
                    if (!dcmp(s.x, t.x) && !dcmp(s.y, t.y)) continue;
51
                    bool f = true;
52
                    for (int k = 1; k <= n; ++k) {
53
                        // cout << s.x << ' ' << s.y << ' ' << t.x << ' ' << t.y << ' ' << a[k].s[0].x << ' ' << a[k].s[0].y << ' ' << a[k].s[1].x << ' ' << a[k].s[1].y << endl;
54
                        if (sign(area(s, t, a[k].s[0])) * sign(area(s, t, a[k].s[1])) > 0) {
55
                            // cout << area(s, t, a[k].s[0]) << ' ' << area(s, t, a[k].s[1]) << endl;
56
                            f = false;
57
                            break;
58
                        }
59
                    }
60
                    // return;
61
                    if (f) {
62
                        printf("Yes!\n");
63
                        return;
64
                    }
65
                }
66
            }
67
        }
68
    }
69
    printf("No!\n");
70
}
71
int main() {
72
    int T;
73
    scanf("%d", &T);
74
    while (T--) {
75
        solve();
76
    }
77
    return 0;
78
}

1
#include <iostream>
2
#include <algorithm>
3
#include <cmath>
4
#define x first
5
#define y second
6
using namespace std;
7
typedef pair<double, double> PDD;
8
const int N = 10010;
9
const double eps = 1e-8;
10
PDD a[N];
11
bool used[N];
12
int st[N], siz;
13

14
PDD operator -(PDD a, PDD b) {
15
    return {a.x - b.x, a.y - b.y};
16
}
17

18
double operator *(PDD a, PDD b) {
19
    return a.x * b.y - a.y * b.x;
20
}
21

22
double area(PDD a, PDD b, PDD c) {
23
    return (b - a) * (c - a);
24
}
25

26
int sign(double val) {
27
    if (fabs(val) < eps) return 0;
28
    else if (val < 0) return -1;
29
    else return 1;
30
}
31

32
double len(PDD a) {
33
    return sqrt(a.x * a.x + a.y * a.y);
34
}
35

36
int main() {
37
    int n;
38
    scanf("%d", &n);
39
    for (int i = 1; i <= n; ++i) {
40
        scanf("%lf%lf", &a[i].x, &a[i].y);
41
    }
42
    sort(a + 1, a + n + 1);
43
    for (int i = 1; i <= n; ++i) {
44
        while (siz >= 2 && sign(area(a[st[siz - 1]], a[st[siz]], a[i])) <= 0) {
45
            if (sign(area(a[st[siz - 1]], a[st[siz]], a[i])) == -1) used[st[siz]] = false;
46
            siz--;
47
        }
48
        st[++siz] = i;
49
        used[i] = true;
50
    }
51
    used[1] = false;
52
    for (int i = n - 1; i; --i) {
53
        if (used[i]) continue;
54
        while (siz >= 2 && sign(area(a[st[siz - 1]], a[st[siz]], a[i])) <= 0) siz--;
55
        st[++siz] = i;
56
    }
57
    cout << siz << endl;
58
    double res = 0;
59
    for (int i = 1; i < siz; ++i) {
60
        res += len(a[st[i]] - a[st[i + 1]]);
61
    }
62
    printf("%.2lf\n", res);
63
    return 0;
64
}

1
#include <iostream>
2
#include <cmath>
3
#include <algorithm>
4
#define x first
5
#define y second
6
using namespace std;
7
typedef long double LD;
8
typedef pair<LD, LD> PDD;
9
const int N = 40010;
10
const LD eps = 1e-18;
11
const LD PI = acosl(-1);
12

13
PDD q[N];
14
int st[N], tp, m;
15
bool used[N];
16

17
PDD operator +(const PDD& a, const PDD& b) {
18
    return {a.x + b.x, a.y + b.y};
19
}
20

21
PDD operator -(const PDD& a, const PDD& b) {
22
    return {a.x - b.x, a.y - b.y};
23
}
24

25
LD operator *(const PDD& a, const PDD& b) {
26
    return a.x * b.y - a.y * b.x;
27
}
28

29
LD len(const PDD& a) {
30
    return sqrtl(a.x * a.x + a.y * a.y);
31
}
32

33
PDD rotate(const PDD& a, LD t) { // 逆时针旋转
34
    return {a.x * cosl(t) - a.y * sinl(t), a.x * sinl(t) + a.y * cosl(t)};
35
}
36

37
LD area(const PDD& a, const PDD& b, PDD c) {
38
    return (b - a) * (c - a);
39
}
40

41
int sign(LD a) {
42
    if (fabsl(a) < eps) return 0;
43
    else if (a < 0) return -1;
44
    else return 1;
45
}
46

47
int main() {
48
    int n;
49
    LD a, b, r;
50
    scanf("%d", &n);
51
    scanf("%Lf%Lf%Lf", &a, &b, &r);
52
    PDD diag[2] = {{b / 2 - r, a / 2 - r}, {r - b / 2, a / 2 - r}};
53
    for (int i = 1; i <= n; ++i) {
54
        LD px, py, t;
55
        scanf("%Lf%Lf%Lf", &px, &py, &t);
56
        q[++m] = PDD(px, py) + rotate(diag[0], t);
57
        q[++m] = PDD(px, py) + rotate(diag[1], t);
58
        q[++m] = PDD(px, py) - rotate(diag[0], t);
59
        q[++m] = PDD(px, py) - rotate(diag[1], t);
60
    }
61
    sort(q + 1, q + m + 1);
62
    for (int i = 1; i <= m; ++i) {
63
        while (tp >= 2 && sign(area(q[st[tp - 1]], q[st[tp]], q[i])) <= 0) {
64
            if (sign(area(q[st[tp - 1]], q[st[tp]], q[i])) == -1) used[st[tp--]] = false;
65
            else tp--;
66
        }
67
        st[++tp] = i;
68
        used[i] = true;
69
    }
70
    used[1] = false;
71
    for (int i = m - 1; i; --i) {
72
        if (used[i]) continue;
73
        while (tp >= 2 && sign(area(q[st[tp - 1]], q[st[tp]], q[i])) <= 0) tp--;
74
        st[++tp] = i;
75
    }
76
    LD res = 0;
77
    for (int i = 1; i < tp; ++i) {
78
        res += len(q[st[i + 1]] - q[st[i]]);
79
    }
80
    printf("%.2Lf\n", res + PI * r * 2);
81
    return 0;
82
}

1
#include <iostream>
2
#include <cmath>
3
#include <algorithm>
4
#define x first
5
#define y second
6
using namespace std;
7
typedef pair<double, double> PDD;
8
const int N = 510;
9
const double eps = 1e-8;
10

11
struct Line {
12
    PDD s, t;
13
} a[N];
14
PDD p[60], ans[N];
15
int q[N];
16

17
int dcmp(double a, double b) {
18
    if (fabs(a - b) < eps) return 0;
19
    else if (a < b) return -1;
20
    else return 1;
21
}
22

23
int sign(double a) {
24
    if (fabs(a) < eps) return 0;
25
    else if (a < 0) return -1;
26
    else return 1;
27
}
28

29
PDD operator -(PDD a, PDD b) {
30
    return {a.x - b.x, a.y - b.y};
31
}
32

33
PDD operator +(PDD a, PDD b) {
34
    return {a.x + b.x, a.y + b.y};
35
}
36

37
PDD operator *(PDD a, double t) {
38
    return {a.x * t, a.y * t};
39
}
40

41
double operator *(PDD a, PDD b) {
42
    return a.x * b.y - a.y * b.x;
43
}
44

45
double area(PDD a, PDD b, PDD c) {
46
    return (b - a) * (c - a);
47
}
48

49
PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w) {
50
    PDD u = p - q;
51
    double t = (w * u) / (v * w);
52
    return p + v * t;
53
}
54

55
PDD get_line_intersection(Line a, Line b) {
56
    return get_line_intersection(a.s, a.t - a.s, b.s, b.t - b.s);
57
}
58

59
double get_angle(Line a) {
60
    return atan2(a.t.y - a.s.y, a.t.x - a.s.x);
61
}
62

63
bool cmp(Line a, Line b) {
64
    double A = get_angle(a), B = get_angle(b);
65
    return dcmp(A, B) ? A < B : area(a.s, a.t, b.s) < 0;
66
}
67

68
bool on_right(Line a, Line b, Line c) {
69
    return sign(area(a.s, a.t, get_line_intersection(b, c))) <= 0;
70
}
71

72
int main() {
73
    int n, m, l = 0;
74
    scanf("%d", &n);
75
    for (int i = 1; i <= n; ++i) {
76
        scanf("%d", &m);
77
        for (int j = 1; j <= m; ++j) {
78
            scanf("%lf%lf", &p[j].x, &p[j].y);
79
        }
80
        for (int j = 1; j < m; ++j) {
81
            a[++l] = {p[j], p[j + 1]};
82
        }
83
        a[++l] = {p[m], p[1]};
84
    }
85
    sort(a + 1, a + l + 1, cmp);
86
    int hh = 0, tt = -1;
87
    for (int i = 1; i <= l; ++i) {
88
        if (i > 1 && !dcmp(get_angle(a[i]), get_angle(a[i - 1]))) continue;
89
        while (hh + 1 <= tt && on_right(a[i], a[q[tt - 1]], a[q[tt]])) tt--;
90
        while (hh + 1 <= tt && on_right(a[i], a[q[hh]], a[q[hh + 1]])) hh++;
91
        q[++tt] = i;
92
    }
93
    while (hh + 1 <= tt && on_right(a[q[hh]], a[q[tt - 1]], a[q[tt]])) tt--;
94
    while (hh + 1 <= tt && on_right(a[q[tt]], a[q[hh]], a[q[hh + 1]])) hh++;
95
    q[++tt] = q[hh];
96
    int len = 0;
97
    for (int i = hh; i < tt; ++i) {
98
        ans[++len] = get_line_intersection(a[q[i]], a[q[i + 1]]);
99
        // cout << q[i] << ' ';
100
    }
101
    // cout << endl;
102
    double res = 0;
103
    for (int i = 2; i < len; ++i) {
104
        res += area(ans[1], ans[i], ans[i + 1]);
105
        // cout << '(' << ans[i].x << ',' << ans[i].y << ')' << ' ';
106
    }
107
    // cout << endl;
108
    res = res / 2;
109
    printf("%.3lf\n", res);
110
    return 0;
111
}

1
#include <iostream>
2
#include <algorithm>
3
#include <vector>
4

5
using namespace std;
6
typedef long long LL;
7
const int N = 10010;
8
struct Node
9
{
10
    LL k, v;
11
    int id;
12
} a[N];
13
int st[N], ans[N], tp;
14
vector<int> t[N];
15

16
int main() {
17
    int n;
18
    scanf("%d", &n);
19
    for (int i = 1; i <= n; ++i) {
20
        scanf("%lld", &a[i].k);
21
        a[i].id = i;
22
    }
23
    for (int i = 1; i <= n; ++i) {
24
        scanf("%lld", &a[i].v);
25
    }
26
    sort(a + 1, a + n + 1, [](Node a, Node b) {
27
        return a.v == b.v ? a.k < b.k : a.v < b.v;
28
    });
29
    for (int i = 1; i <= n; ++i) {
30
        while (tp > 1 && (a[i].k - a[st[tp]].k) * (a[st[tp - 1]].v - a[st[tp]].v) < (a[st[tp]].k - a[st[tp - 1]].k) * (a[st[tp]].v - a[i].v) || tp && a[i].k > a[st[tp]].k) tp--;
31
        st[++tp] = i;
32
    }
33
    for (int i = 1; i <= tp; ++i) {
34
        ans[i] = a[st[i]].id;
35
    }
36
    sort(ans + 1, ans + tp + 1);
37
    printf("%d\n", tp);
38
    for (int i = 1; i <= tp; ++i) {
39
        if (i == 1) printf("%d", ans[i]);
40
        else printf(" %d", ans[i]);
41
    }
42
    printf("\n");
43
    return 0;
44
}

1
#include <iostream>
2
#include <algorithm>
3
#include <cmath>
4
#define x first
5
#define y second
6
using namespace std;
7
typedef long long LL;
8
typedef pair<LL, LL> PLL;
9
const int N = 50010;
10
PLL a[N];
11
int st[N], tp;
12
bool used[N];
13

14
PLL operator -(PLL a, PLL b) {
15
    return {a.x - b.x, a.y - b.y};
16
}
17

18
LL operator *(PLL a, PLL b) {
19
    return a.x * b.y - a.y * b.x;
20
}
21

22
LL area(PLL a, PLL b, PLL c) {
23
    return (b - a) * (c - a);
24
}
25

26
LL get_dis(PLL a, PLL b) {
27
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
28
}
29

30
int main() {
31
    int n;
32
    scanf("%d", &n);
33
    for (int i = 1; i <= n; ++i) {
34
        scanf("%lld%lld", &a[i].x, &a[i].y);
35
    }
36
    sort(a + 1, a + n + 1);
37
    for (int i = 1; i <= n; ++i) {
38
        while (tp > 1 && area(a[st[tp - 1]], a[st[tp]], a[i]) <= 0) {
39
            if (area(a[st[tp - 1]], a[st[tp]], a[i]) < 0) used[st[tp]] = false;
40
            tp--;
41
        }
42
        st[++tp] = i;
43
        used[i] = true;
44
    }
45
    used[1] = false;
46
    for (int i = n - 1; i; --i) {
47
        if (used[i]) continue;
48
        while (tp > 1 && area(a[st[tp - 1]], a[st[tp]], a[i]) <= 0) tp--;
49
        st[++tp] = i;
50
    }
51
    tp--;
52
    if (tp <= 2) {
53
        printf("%lld\n", get_dis(a[1], a[n]));
54
    }
55
    else {
56
        LL res = 0;
57
        for (int i = 1, j = 3; i < tp; ++i) {
58
            while (area(a[st[i]], a[st[i + 1]], a[st[j]]) <= area(a[st[i]], a[st[i + 1]], a[st[j % (tp - 1) + 1]])) j = j % (tp - 1) + 1;
59
            res = max(res, max(get_dis(a[st[i]], a[st[j]]), get_dis(a[st[i + 1]], a[st[j]])));
60
        }
61
        printf("%lld\n", res);
62
    }
63
    return 0;
64
}

1
#include <iostream>
2
#include <cmath>
3
#include <algorithm>
4
#define x first
5
#define y second
6

7
using namespace std;
8

9
typedef pair<double, double> PDD;
10
const int N = 50010;
11
const double eps = 1e-12;
12
const double PI = acos(-1);
13

14
PDD a[N];
15
int st[N], tp;
16
bool used[N];
17

18
int sign(double a) {
19
    if (fabs(a) < eps) return 0;
20
    else if (a < 0) return -1;
21
    else return 1;
22
}
23

24
int dcmp(double a, double b) {
25
    if (fabs(a - b) < eps) return 0;
26
    else if (a < b) return -1;
27
    else return 1;
28
}
29

30
PDD operator +(PDD a, PDD b) {
31
    return {a.x + b.x, a.y + b.y};
32
}
33

34
PDD operator -(PDD a, PDD b) {
35
    return {a.x - b.x, a.y - b.y};
36
}
37

38
PDD operator *(PDD a, double b) {
39
    return {a.x * b, a.y * b};
40
}
41

42
PDD operator /(PDD a, double b) {
43
    return {a.x / b, a.y / b};
44
}
45

46
double operator *(PDD a, PDD b) {
47
    return a.x * b.y - a.y * b.x;
48
}
49

50
double operator &(PDD a, PDD b) {
51
    return a.x * b.x + a.y * b.y;
52
}
53

54
double area(PDD a, PDD b, PDD c) {
55
    return (b - a) * (c - a);
56
}
57

58
double getlen(PDD a) {
59
    return sqrt(pow(a.x, 2) + pow(a.y, 2));
60
}
61

62
double proj(PDD a, PDD b, PDD c) { // proj_(b - a) (c - b)
63
    return ((b - a) & (c - b)) / getlen(b - a);
64
}
65

66
PDD rotate(PDD a, double t) {
67
    return {a.x * cos(t) - a.y * sin(t), a.x * sin(t) + a.y * cos(t)};
68
}
69

70
PDD unit(PDD a) {
71
    return a / getlen(a);
72
}
73

74
ostream &operator <<(ostream &cout, const PDD &a) {
75
    cout << '(' << a.x << ',' << a.y << ')';
76
    return cout;
77
}
78

79
int main() {
80
    int n;
81
    scanf("%d", &n);
82
    for (int i = 1; i <= n; ++i) {
83
        scanf("%lf%lf", &a[i].x, &a[i].y);
84
    }
85
    sort(a + 1, a + n + 1);
86
    for (int i = 1; i <= n; ++i) {
87
        while (tp > 1 && sign(area(a[st[tp - 1]], a[st[tp]], a[i])) <= 0) {
88
            if (sign(area(a[st[tp - 1]], a[st[tp]], a[i])) == -1) used[st[tp]] = false;
89
            tp--;
90
        }
91
        st[++tp] = i;
92
        used[i] = true;
93
    }
94
    used[1] = false;
95
    for (int i = n; i; --i) {
96
        if (used[i]) continue;
97
        while (tp > 1 && sign(area(a[st[tp - 1]], a[st[tp]], a[i])) <= 0) tp--;
98
        st[++tp] = i;
99
    }
100
    tp--;
101
    double res = 1e18;
102
    PDD p[4];
103
    // for (int i = 1; i <= tp; ++i) cout << a[st[i]] << ' ';
104
    // cout << endl;
105
    for (int i = 1, j = 3, k = 2, l = 3; i < tp; ++i) {
106
        PDD &c = a[st[i]], &d = a[st[i + 1]];
107
        while (dcmp(area(c, d, a[st[j]]), area(c, d, a[st[j % tp + 1]])) < 0) j = j % tp + 1;
108
        while (dcmp(proj(c, d, a[st[k]]), proj(c, d, a[st[k % tp + 1]])) < 0) k = k % tp + 1;
109
        if (i == 1) l = j;
110
        while (dcmp(proj(c, d, a[st[l]]), proj(c, d, a[st[l % tp + 1]])) > 0) l = l % tp + 1;
111
        PDD &e = a[st[k]], &f = a[st[j]], &g = a[st[l]];
112
        double h = area(c, d, f) / getlen(d - c), w = ((e - g) & (d - c)) / getlen(d - c);
113
        if (dcmp(res, h * w) > 0) {
114
            res = h * w;
115
            PDD dh = unit(rotate(d - c, PI / 2)) * h;
116
            p[0] = d + unit(d - c) * proj(c, d, g);
117
            p[1] = d + unit(d - c) * proj(c, d, e);
118
            p[2] = p[1] + dh;
119
            p[3] = p[0] + dh;
120
        }
121
    }
122
    printf("%.5lf\n", res);
123
    int fir = 0;
124
    for (int i = 0; i < 4; ++i) {
125
        // -0.00000 不要背刺我😭
126
        if (sign(p[i].x) == 0) p[i].x = 0;
127
        if (sign(p[i].y) == 0) p[i].y = 0;
128
        if (dcmp(p[fir].y, p[i].y) == 1) fir = i;
129
        else if (dcmp(p[fir].y, p[i].y) == 0 && dcmp(p[fir].x, p[i].x) == 1) fir = i;
130
    }
131
    for (int i = 0; i < 4; ++i) {
132
        printf("%.5lf %.5lf\n", p[(i + fir) % 4].x, p[(i + fir) % 4].y);
133
    }
134
    return 0;
135
}

1
#include <iostream>
2
#include <algorithm>
3
#include <vector>
4
#define x first
5
#define y second
6

7
using namespace std;
8
typedef long long LL;
9
typedef pair<int, int> PII;
10
const int N = 1010;
11
PII a[N], b[N], t[N];
12
vector<int> values;
13
int n;
14

15
LL work(int l, int r) {
16
    int len = 0;
17
    for (int i = 1; i <= n; ++i) {
18
        if (a[i].x <= l && b[i].x >= r) {
19
            t[++len] = {a[i].y, b[i].y};
20
        }
21
    }
22
    if (!len) return 0; // 空的
23
    sort(t + 1, t + len + 1);
24
    LL res = 0;
25
    int L = t[1].x, R = t[1].y;
26
    for (int i = 2; i <= len; ++i) {
27
        if (t[i].x <= R) {
28
            R = max(R, t[i].y);
29
        }
30
        else {
31
            res += R - L;
32
            L = t[i].x, R = t[i].y;
33
        }
34
    }
35
    res += R - L;
36
    return res * (r - l);
37
}
38

39
int main() {
40
    scanf("%d", &n);
41
    for (int i = 1; i <= n; ++i) {
42
        scanf("%d%d%d%d", &a[i].x, &a[i].y, &b[i].x, &b[i].y);
43
        values.emplace_back(a[i].x), values.emplace_back(b[i].x);
44
    }
45
    sort(values.begin(), values.end());
46
    int m = values.size() - 1;
47
    LL res = 0;
48
    for (int i = 0; i < m; ++i) {
49
        if (values[i] != values[i + 1])
50
            res += work(values[i], values[i + 1]);
51
    }
52
    printf("%lld\n", res);
53
    return 0;
54
}