长春寒假集训模拟赛 Ⅲ

2016.01.22 20:39 Fri| 33 visits oi_2016| 2016_竞赛日常| Text

矩形

题目大意

给出一个中心在原点,边平行于坐标轴的矩形的长和宽。将它旋转一个角度,问新矩形与原矩形的交的面积。

题解

简单的半平面交裸上。

 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
#include <bits/stdc++.h>
using namespace std;

#define sqr(x) ((x) * (x))
#define dcmp(x) (fabs(x) < 1e-8)
#define pi 3.14159265358979323

struct point
{
    double x, y;
    point(double _x = 0.0, double _y = 0.0) : x(_x), y(_y) {}
    bool operator <(const point &p) const
    { return x == p.x ? y < p.y : x < p.x; }
    point operator +(point p) { return point(x + p.x, y + p.y); }
    point operator -(point p) { return point(x - p.x, y - p.y); }
    point operator *(double d) { return point(x * d, y * d); }
    friend double cross(point a, point b) { return a.x * b.y - a.y * b.x; }
    friend point rotate(point p, double a)
    { return point(p.x * cos(a) - p.y * sin(a), p.x * sin(a) + p.y * cos(a)); }
};

struct line
{
    point p, v; double t;
    line() {}
    line(point _p, point _v) : p(_p), v(_v) { t = atan2(v.y, v.x); }
    bool operator <(const line &l) const
    { return dcmp(t - l.t) ? onleft(p, l) : t < l.t; }
    friend bool onleft(point p, line l) { return cross(l.v, p - l.p) > -1e-8; }
    friend point intersection(line a, line b)
    { return a.p + a.v * (cross(b.v, a.p - b.p) / cross(a.v, b.v)); }
};

double half_plane_intersection(int n, line l[])
{
    deque<pair<line, point> > q;
    sort(l + 1, l + n + 1);
    q.push_back(make_pair(l[1], point()));
    for (int i = 2; i <= n; ++i)
    {
        if (dcmp(l[i].t - l[i - 1].t)) continue;
        while (q.size() > 1 && !onleft(q.back().second, l[i])) q.pop_back();
        while (q.size() > 1 && !onleft(q[1].second, l[i])) q.pop_front();
        q.push_back(make_pair(l[i], intersection(l[i], q.back().first)));
    }
    while (q.size() > 1 && !onleft(q.back().second, q[0].first)) q.pop_back();
    q.front().second = intersection(q.front().first, q.back().first);
    double re = 0;
    for (int i = 2; i < (int)q.size(); ++i)
        re += cross(q[i - 1].second - q[0].second, q[i].second - q[0].second);
    return re;
}

double w, h, a;
point p[10], q[10]; line l[10];

int main()
{
    freopen("rect.in", "r", stdin);
    freopen("rect.out", "w", stdout);
    cin >> w >> h >> a;
    p[1] = point(w / 2, h / 2), q[1] = rotate(p[1], a / 180 * pi);
    p[2] = point(-w / 2, h / 2), q[2] = rotate(p[2], a / 180 * pi);
    p[3] = point(-w / 2, -h / 2), q[3] = rotate(p[3], a / 180 * pi);
    p[4] = point(w / 2, -h / 2), q[4] = rotate(p[4], a / 180 * pi);
    l[1] = line(p[1], p[2] - p[1]), l[5] = line(q[1], q[2] - q[1]);
    l[2] = line(p[2], p[3] - p[2]), l[6] = line(q[2], q[3] - q[2]);
    l[3] = line(p[3], p[4] - p[3]), l[7] = line(q[3], q[4] - q[3]);
    l[4] = line(p[4], p[1] - p[4]), l[8] = line(q[4], q[1] - q[4]);
    cout << fixed << setprecision(9);
    cout << fabs(half_plane_intersection(8, l)) / 2 << endl;
    return 0;
}

历史

题目大意

不务正业的国王爱生气死得快的狗血语文题!

题解

将询问离线,维护一个并查集直接扫过去就好了。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 300005

int n, m, fa[N], type[N], x[N], y[N], ans1[N], ans2[N];
vector<int> q[N]; char opt[5];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int find(int x)
{
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

int main()
{
    freopen("history.in", "r", stdin);
    freopen("history.out", "w", stdout);
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        fa[i] = i;
    for (int i = 1, tot = 0; i <= m; ++i)
    {
        scanf("%s", opt);
        if (opt[0] == 'K')
        {
            type[i] = 1, x[i] = read();
        }
        else if (opt[0] == 'R')
        {
            type[i] = 2, x[i] = read(), y[i] = read();
            ++tot;
        }
        else
        {
            type[i] = 3, x[i] = read(), y[i] = read();
            int t = read();
            if (t >= tot) ans2[i] = (x[i] == y[i]);
            else q[tot - t].push_back(i);
        }
    }
    for (int i = 1, c = 0, flag = 0, tot = 0; i <= m; ++i)
    {
        if (type[i] == 1)
        {
            c = x[i], flag = false;
        }
        else if (type[i] == 2)
        {
            if (flag)
                x[i] = (x[i] + c) % n, y[i] = (y[i] + c) % n;
            if (find(x[i]) != find(y[i]))
                fa[find(x[i])] = find(y[i]);
            ++tot;
            for (int j = 0, k; j < (int)q[tot].size(); ++j)
                k = q[tot][j], ans2[k] = (find(x[k]) == find(y[k]));
        }
        else
        {
            ans1[i] = (find(x[i]) == find(y[i]));
            flag = false;
            if (ans1[i] && !ans2[i]) puts("Y");
            else puts("N"), flag = true;
        }
    }
    return 0;
}

BZOJ3975 [WF2012]Asteroid Rangers

题解

我们可以将每两个小行星之间都看作有一条边,而边的长度是时时刻刻变化着的。我们需要维护的就是它们之间最小生成树的变化情况。容易发现,边的长度是关于时间的二次以内函数,而对于两条边,我们可以接出来在哪些时刻时,它们的相对长度发生了变化。

如果两条边的大小关系发生改变,其中一条边是之前的树边而另一条不是,但另一条边也可连接第一条边两端的连通块,那么我们需要将第一条边踢出最小生成树,将第二条边加进来。每当最小生成树发生变化,我们可以重新搜索出它的 DFS 序。这样,判断两条边的关系就可以在 O(1) 的时间内实现了。实际上,最小生成树变化的次数并不会很多,所以可以通过所有测试数据。

  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
#include <bits/stdc++.h>
using namespace std;

#define N 55
#define sqr(x) ((x) * (x))

int n, x[N], y[N], z[N], vx[N], vy[N], vz[N];
int con[N][N], id[N], id2[N], ans;

struct quad
{
    int x, y, z, w;
    quad(int _x, int _y, int _z, int _w) : x(_x), y(_y), z(_z), w(_w) {}
    bool operator <(const quad &q) const { return x < q.x; }
    friend ostream &operator <<(ostream &out, quad q)
    { out << "(" << q.x << ", " << q.y << ", "
        << q.z << ", " << q.w << ")"; return out; }
};

struct edge
{
    int a, b, c;
    edge() {}
    edge(int _a, int _b, int _c) : a(_a), b(_b), c(_c) {}
    int check() { if (a) return 2; if (b) return 1; return 0; }
    edge operator -(edge &e) { return edge(a - e.a, b - e.b, c - e.c); }
    friend ostream &operator <<(ostream &out, edge e)
    { out << "(" << e.a << ", " << e.b << ", " << e.c << ")"; return out; }
} len[N * N];

vector<pair<double, quad> > v;

inline int pos(int a, int b) { return a * n + b; }

void gettime(int a, int b, quad q)
{
    edge t = len[a] - len[b];
    if (t.check() == 0) return;
    if (t.check() == 1)
    {
        if (-1.0 * t.c / t.b > 0)
            v.push_back(make_pair(-1.0 * t.c / t.b, q));
        return;
    }
    double delta = t.b * t.b - 4 * t.a * t.c;
    if (delta <= 0) return;
    delta = sqrt(delta);
    if (0.5 * (-t.b - delta) / t.a > 0)
            v.push_back(make_pair(0.5 * (-t.b - delta) / t.a, q));
    if (0.5 * (-t.b + delta) / t.a > 0)
        v.push_back(make_pair(0.5 * (-t.b + delta) / t.a, q));
}

double dist(int a, int b, double t)
{
    return sqr(x[a] - x[b] + t * (vx[a] - vx[b]))
         + sqr(y[a] - y[b] + t * (vy[a] - vy[b]))
         + sqr(z[a] - z[b] + t * (vz[a] - vz[b]));
}

bool checkdis(int i)
{
    if (dist(v[i].second.x, v[i].second.y, v[i].first + 1e-6) <
        dist(v[i].second.z, v[i].second.w, v[i].first + 1e-6))
        return false;
    return true;
}

int find(int fa[], int x)
{
    if (x == fa[x]) return x;
    return fa[x] = find(fa, fa[x]);
}

void kruskal()
{
    vector<pair<int, pair<int, int> > > v;
    int fa[N];
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            v.push_back(make_pair(dist(i, j, 0), make_pair(i, j)));
    sort(v.begin(), v.end());
    for (int i = 0; i < (int)v.size(); ++i)
    {
        int x = v[i].second.first, y = v[i].second.second;
        if (find(fa, x) != find(fa, y))
            fa[find(fa, x)] = find(fa, y), con[x][y] = con[y][x] = 1;
    }
}

void dfs(int x, int fa)
{
    static int tot;
    if (fa == 0) tot = 0;
    id[x] = ++tot;
    for (int i = 1; i <= n; ++i)
        if (i != fa && con[x][i]) dfs(i, x);
    id2[x] = tot;
}

bool onpath(quad q)
{
    int t = id[q.x] < id[q.y] ? q.y : q.x;
    if (((id[q.z] >= id[t] && id[q.z] <= id2[t]) &&
        (id[q.w] < id[t] || id[q.w] > id2[t])) ||
        ((id[q.w] >= id[t] && id[q.w] <= id2[t]) &&
        (id[q.z] < id[t] || id[q.z] > id2[t])))
        return true;
    return false;
}

void init()
{
    memset(con, 0, sizeof con);
    ans = 0, v.clear();
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    for (int test = 1; cin >> n; ++test)
    {
        for (int i = 1; i <= n; ++i)
            x[i] = read(), y[i] = read(), z[i] = read(),
            vx[i] = read(), vy[i] = read(), vz[i] = read();
        init();
        for (int i = 1; i <= n; ++i)
            for (int j = i + 1; j <= n; ++j)
                len[pos(i, j)] = edge(  sqr(vx[i] - vx[j])
            /*そのコードはきれいだ*/  + sqr(vy[i] - vy[j])
            /*そのコードはきれいだ*/  + sqr(vz[i] - vz[j]),
            /*そのコードはきれいだ*/    2 * (x[i] - x[j]) * (vx[i] - vx[j])
            /*そのコードはきれいだ*/  + 2 * (y[i] - y[j]) * (vy[i] - vy[j])
            /*そのコードはきれいだ*/  + 2 * (z[i] - z[j]) * (vz[i] - vz[j]),
            /*そのコードはきれいだ*/    sqr(x[i] - x[j])
            /*そのコードはきれいだ*/  + sqr(y[i] - y[j])
            /*そのコードはきれいだ*/  + sqr(z[i] - z[j]));
        for (int i = 1; i <= n; ++i) for (int j = i + 1; j <= n; ++j)
            for (int k = 1; k <= n; ++k) for (int l = k + 1; l <= n; ++l)
                if (k != i || l != j)
                    gettime(pos(i, j), pos(k, l), quad(i, j, k, l));
        sort(v.begin(), v.end());
        kruskal(), dfs(1, 0);
        for (int i = 0; i < (int)v.size(); ++i)
            if (con[v[i].second.x][v[i].second.y] &&
                !con[v[i].second.z][v[i].second.w] &&
                checkdis(i) && onpath(v[i].second))
            {
                if (isinf(v[i].first)) continue;
                con[v[i].second.x][v[i].second.y] = 0,
                con[v[i].second.y][v[i].second.x] = 0;
                con[v[i].second.z][v[i].second.w] = 1,
                con[v[i].second.w][v[i].second.z] = 1;
                dfs(1, 0), ++ans;
            }
        printf("Case %d: %d\n", test, ans + 1);
    }
    return 0;
}