Chaos Slover 补档计划 - 计算几何(3 扫描线、解析几何)

2015.12.21 12:57 Mon| 7 visits oi_2016| ChaosSlover补档计划| Text

POJ1389 Area of Simple Polygons

简单的求矩形面积并。

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

struct data
{
    int l, d, r, u;
    bool check() { return l != -1; }
    friend istream &operator >>(istream &in, data &d)
    { in >> d.l >> d.d >> d.r >> d.u; return in; }
};

#define lson (pos << 1)
#define rson (pos << 1 | 1)

int n, sum[200005], tag[200005];
data d[1005];
vector<pair<int, int> > p1[50005], p2[50005];

void insert(int pos, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y)
    {
        tag[pos] += z;
    }
    else
    {
        int mid = (l + r) >> 1;
        if (x <= mid) insert(lson, l, mid, x, y, z);
        if (y > mid) insert(rson, mid + 1, r, x, y, z);
    }
    if (tag[pos] >= 1) sum[pos] = r - l + 1;
    else sum[pos] = sum[lson] + sum[rson];
}

int main()
{
    while (cin >> d[n = 1], d[1].check())
    {
        while (cin >> d[n + 1], d[n + 1].check()) ++n;
        for (int i = 0; i <= 50000; ++i)
            p1[i].resize(0), p2[i].resize(0);
        for (int i = 1; i <= n; ++i)
            p1[d[i].l].push_back(make_pair(d[i].d, d[i].u - 1)),
            p2[d[i].r].push_back(make_pair(d[i].d, d[i].u - 1));
        unsigned int ans = 0;
        memset(sum, 0, sizeof sum);
        memset(tag, 0, sizeof tag);
        for (int i = 0; i <= 50000; ++i)
        {
            ans += sum[1];
            for (int j = 0; j < (int)p1[i].size(); ++j)
                insert(1, 0, 50000, p1[i][j].first, p1[i][j].second, 1);
            for (int j = 0; j < (int)p2[i].size(); ++j)
                insert(1, 0, 50000, p2[i][j].first, p2[i][j].second, -1);
        }
        cout << ans << endl;
    }
    return 0;
}

POJ1177 Picture

求矩形交的周长,分别求出横向边的总长度和纵向边的总长度,然后加起来就是答案。由姑且叫做对称性的东西,可以只求出加入边的时候增加的长度,最后答案 *2。

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

struct data
{
    int l, d, r, u;
    bool check() { return l != -1; }
    friend istream &operator >>(istream &in, data &d)
    {
        in >> d.l >> d.d >> d.r >> d.u;
        d.l += 10000; d.d += 10000; d.r += 10000; d.u += 10000;
        return in;
    }
};

#define lson (pos << 1)
#define rson (pos << 1 | 1)

int n, sum[160005], tag[160005];
data d[5005];
vector<pair<int, int> > p1[20005], p2[20005];

void insert(int pos, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y)
    {
        tag[pos] += z;
    }
    else
    {
        int mid = (l + r) >> 1;
        if (x <= mid) insert(lson, l, mid, x, y, z);
        if (y > mid) insert(rson, mid + 1, r, x, y, z);
    }
    if (tag[pos] >= 1) sum[pos] = r - l + 1;
    else sum[pos] = sum[lson] + sum[rson];
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> d[i];
    for (int i = 1; i <= n; ++i)
    {
        p1[d[i].l].push_back(make_pair(d[i].d, d[i].u - 1)),
        p2[d[i].r].push_back(make_pair(d[i].d, d[i].u - 1));
    }
    int ans = 0;
    for (int i = 0; i <= 20000; ++i)
    {
        int t = sum[1];
        for (int j = 0; j < (int)p1[i].size(); ++j)
            insert(1, 0, 20000, p1[i][j].first, p1[i][j].second, 1);
        ans += abs(t - sum[1]);
        for (int j = 0; j < (int)p2[i].size(); ++j)
            insert(1, 0, 20000, p2[i][j].first, p2[i][j].second, -1);
        p1[i].resize(0);
        p2[i].resize(0);
    }
    for (int i = 1; i <= n; ++i)
    {
        p1[d[i].d].push_back(make_pair(d[i].l, d[i].r - 1)),
        p2[d[i].u].push_back(make_pair(d[i].l, d[i].r - 1));
    }
    memset(tag, 0, sizeof tag);
    memset(sum, 0, sizeof sum);
    for (int i = 0; i <= 20000; ++i)
    {
        int t = sum[1];
        for (int j = 0; j < (int)p1[i].size(); ++j)
            insert(1, 0, 20000, p1[i][j].first, p1[i][j].second, 1);
        ans += abs(t - sum[1]);
        for (int j = 0; j < (int)p2[i].size(); ++j)
            insert(1, 0, 20000, p2[i][j].first, p2[i][j].second, -1);
    }
    cout << ans * 2 << endl;
    return 0;
}

POJ3565 Ants

计算几何的调整思想,看起来其实挺像骗分的。就是当不符合题意的时候,就不听地 N^2 搞来搞去。

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

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

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 dot(point a, point b) { return a.x * b.x + a.y * b.y; }
    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)); }
    friend double dist(point a, point b)
    { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }   
    friend istream &operator >>(istream &in, point &p)
    { in >> p.x >> p.y; return in; }
    friend ostream &operator <<(ostream &out, point p)
    { out << '(' << p.x << ", " << p.y << ')'; return out; }
};

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

bool intersec(line a, line b)
{
    if (onleft(a.p, b) + onleft(a.p + a.v, b) != 1) return false;
    if (onleft(b.p, a) + onleft(b.p + b.v, a) != 1) return false;
    return true;
}

int n, ans[105];
point a[105], b[105];
line l[105];

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        cin >> b[i], ans[i] = i, l[i] = line(a[i], b[i] - a[i]);
    while (true)
    {
        bool flag = true;
        for (int i = 1; i <= n; ++i)
            for (int j = i + 1; j <= n; ++j)
                if (intersec(l[i], l[j]))
                    flag = false, swap(ans[i], ans[j]),
                    l[i] = line(a[i], b[ans[i]] - a[i]),
                    l[j] = line(a[j], b[ans[j]] - a[j]);
        if (flag) break;
    }
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << endl;
    return 0;
}

POJ2002 Squares

简单的枚举正方形对角线。

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

int n, x[1005], y[1005];
set<pair<int, int> > s;

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()
{
    while (cin >> n, n)
    {
        s.clear();
        for (int i = 1; i <= n; ++i)
            x[i] = read(), y[i] = read(), s.insert(make_pair(x[i], y[i]));
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = i + 1; j <= n; ++j)
            {
                double tx = 1.0 * (x[i] + x[j]) / 2,
                       ty = 1.0 * (y[i] + y[j]) / 2;
                double dx = x[i] - tx, dy = y[i] - ty;
                if (fabs(tx + dy - int(tx + dy)) < 0.4 && 
                    fabs(ty + dx - int(ty + dx)) < 0.4 &&
                    s.find(make_pair(int(tx - dy), int(ty + dx))) != s.end() &&
                    s.find(make_pair(int(tx + dy), int(ty - dx))) != s.end())
                    ++ans;
            }
        cout << ans / 2 << endl;
    }
    return 0;
}

POJ1434 Fill the Cisterns!

一道二分答案的水题。

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

int test, n, tot, s[50005], b[50005], h[50005];

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

double check(double mid)
{
    double re = 0;
    for (int i = 1; i <= n; ++i)
        if (mid >= b[i])
            re += s[i] * min((double)h[i], mid - b[i]);
    return re;
}

int main()
{
    cin >> test;
    while (test--)
    {
        cin >> n;
        double l = 0, r = 0, sum = 0;
        for (int i = 1; i <= n; ++i)
            b[i] = read(), h[i] = read(), s[i] = read() * read(),
            r = max(r, (double)b[i] + h[i]), sum += s[i] * h[i];
        cin >> tot;
        if (sum < tot) { puts("OVERFLOW"); continue; }
        double ans = r;
        while (l + 1e-3 < r)
        {
            double mid = (l + r) / 2;
            if (check(mid) < tot) l = mid;
            else ans = mid, r = mid;
        }
        cout << fixed << setprecision(2) << ans << endl;
    }
    return 0;
}

POJ1375 Intervals

给出一个光源和一堆圆,求地上的阴影区间。

对于每一个圆分别求出来阴影的左端点和右端点,然后排序之后简单合并一下。并不困难,嗯。并不困难。

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

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

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 dot(point a, point b) { return a.x * b.x + a.y * b.y; }
    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)); }
    friend double dist(point a, point b)
    { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }   
    friend istream &operator >>(istream &in, point &p)
    { in >> p.x >> p.y; return in; }
    friend ostream &operator <<(ostream &out, point p)
    { out << '(' << p.x << ", " << p.y << ')'; return out; }
};

int n, r;
point p, q;
pair<double, double> shade[505];

int main()
{
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(2);
    while (cin >> n, n)
    {
        cin >> p;
        for (int i = 1; i <= n; ++i)
        {
            cin >> q >> r;
            double d = dist(p, q);
            point v = rotate(q - p, -asin(r / d));
            double l = (p - v * (p.y / v.y)).x;
            v = rotate(q - p, asin(r / d));
            double r = (p - v * (p.y / v.y)).x;
            shade[i] = make_pair(l, r);
        }
        sort(shade + 1, shade + n + 1);
        cout << shade[1].first << ' ';
        double maxd = shade[1].second;
        for (int i = 2; i <= n; ++i)
        {
            if (shade[i].first > maxd)
                cout << maxd << '\n' << shade[i].first << ' ';
            maxd = max(maxd, shade[i].second);
        }
        cout << maxd << '\n' << endl;
    }
    return 0;
}

POJ1329 Circle Through Three Points

外接圆圆心就是三角形的外心就是边的垂直平分线的交点。再加上作死的输出。

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

#define sqr(x) ((x) * (x))
#define dcmp(x) (fabs(x) < 1e-8)
#define pi 3.1415926535
#define sign(x) ((x) < 0 ? '-' : '+')

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 dot(point a, point b) { return a.x * b.x + a.y * b.y; }
    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)); }
    friend double dist(point a, point b)
    { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }   
    friend istream &operator >>(istream &in, point &p)
    { in >> p.x >> p.y; return in; }
    friend ostream &operator <<(ostream &out, point p)
    { out << '(' << p.x << ", " << p.y << ')'; return out; }
};

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

point a, b, c;

int main()
{
    while (cin >> a >> b >> c)
    {
        line l1 = line(a + (b - a) * 0.5, rotate(b - a, pi / 2));
        line l2 = line(b + (c - b) * 0.5, rotate(c - b, pi / 2));
        point m = intersection(l1, l2);
        printf("(x %c %.3f)^2 + (y %c %.3f)^2 = %.3f^2\n",
            sign(-m.x), fabs(m.x), sign(-m.y), fabs(m.y), dist(a, m));
        printf("x^2 + y^2 %c %.3fx %c %.3fy %c %.3f = 0\n\n",
            sign(-m.x), 2 * fabs(m.x), sign(-m.y), 2 * fabs(m.y),
            sign(m.x * m.x + m.y * m.y - dist(a, m) * dist(a, m)),
            fabs(m.x * m.x + m.y * m.y - dist(a, m) * dist(a, m)));
    }
    return 0;
}

POJ1106 Transmitters

已加上不被卡常数的 buff。

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

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

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 dot(point a, point b) { return a.x * b.x + a.y * b.y; }
    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)); }
    friend double dist(point a, point b)
    { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }   
    friend istream &operator >>(istream &in, point &p)
    { in >> p.x >> p.y; return in; }
    friend ostream &operator <<(ostream &out, point p)
    { out << '(' << p.x << ", " << p.y << ')'; return out; }
};

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

int n;
double r;
point c, p[155];
line l[305];

int main()
{
    ios::sync_with_stdio(false);
    while (cin >> c >> r)
    {
        if (!(cin >> n)) break;
        int tot = 0, tl = 0, tr = 1, ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            cin >> p[i];
            if (dist(c, p[i]) <= r) l[++tot] = line(c, p[i] - c);
        }
        sort(l + 1, l + tot + 1);
        for (int i = 1; i <= tot; ++i)
            l[i + tot] = l[i], l[i + tot].t += 2 * pi;
        while (++tl <= tot)
        {
            while (tr + 1 < tl + tot && l[tr + 1].t <= l[tl].t + pi) ++tr;
            ans = max(ans, tr - tl + 1);
        }
        cout << ans << endl;
    }
    return 0;
}

POJ1673 EXOCENTER OF A TRIANGLE

初中几何一顿证,发现就是求垂心。输出还要加一个 eps,码淡!

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

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

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 dot(point a, point b) { return a.x * b.x + a.y * b.y; }
    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)); }
    friend double dist(point a, point b)
    { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }   
    friend istream &operator >>(istream &in, point &p)
    { in >> p.x >> p.y; return in; }
    friend ostream &operator <<(ostream &out, point p)
    { out << p.x + 1e-8 << ' ' << p.y + 1e-8; return out; }
};

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

int n;
point a, b, c;

int main()
{
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(4);
    cin >> n;
    while (n--)
    {
        cin >> a >> b >> c;
        line l1 = line(intersection(line(a, b - a),
                                    line(c, rotate(b - a, pi / 2))),
                       rotate(b - a, pi / 2));
        line l2 = line(intersection(line(b, c - b),
                                    line(a, rotate(c - b, pi / 2))),
                       rotate(c - b, pi / 2));
        cout << intersection(l1, l2) << endl;
    }
    return 0;
}

POJ2187 Beauty Contest

注意各种细节:凸包上不保留共线点,旋转卡壳的跨度要尽可能小。

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

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

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 dot(point a, point b) { return a.x * b.x + a.y * b.y; }
    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)); }
    friend double dist(point a, point b)
    { return sqr(a.x - b.x) + sqr(a.y - b.y); }
    friend istream &operator >>(istream &in, point &p)
    { in >> p.x >> p.y; return in; }
    friend ostream &operator <<(ostream &out, point p)
    { out << '(' << p.x << ", " << p.y << ')'; return out; }
};

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

inline bool check(vector<point> &q, point &p)
{
    point temp = q.back(); q.pop_back();
    if (cross(temp - q.back(), p - temp) < 1e-8)
        return false;
    q.push_back(temp); return true;
}

vector<point> convex_hull(int n, point p[])
{
    vector<point> q;
    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; ++i)
    {
        while ((int)q.size() > 1 && !check(q, p[i]));
        q.push_back(p[i]);
    }
    int temp = q.size();
    for (int i = n - 1; i; --i)
    {
        while ((int)q.size() > temp && !check(q, p[i]));
        q.push_back(p[i]);
    }
    return q;
}

double maxdist(vector<point> q)
{
    static line l[50005];
    double re = 0;
    int n = q.size() - 1;
    for (int i = 0; i < n; ++i)
        l[i] = line(q[i], q[i + 1] - q[i]);
    for (int i = 0, j = 1; i < n; ++i)
    {
        while ((j + 1) % n != i && cross(l[i].v, l[j].v) > 1e-8)
            j = (j + 1) % n;
        re = max(re, dist(q[i], q[j]));
    }
    return re;
}

int n;
point p[50005];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> p[i];
    cout << (int)maxdist(convex_hull(n, p)) << endl;
    return 0;
}

POJ3608 Bridge Across Islands

旋转卡壳,分别枚举两个凸包上的每一条边,之后在另一个凸包上找到反向平行线,计算距离并更新答案。

答案的初始值一定要开大啊 QAQ。凭什么 1e10 都不让过!

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

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

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 dot(point a, point b) { return a.x * b.x + a.y * b.y; }
    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)); }
    friend double dist(point a, point b)
    { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }
    friend istream &operator >>(istream &in, point &p)
    { in >> p.x >> p.y; return in; }
    friend ostream &operator <<(ostream &out, point p)
    { out << '(' << p.x << ", " << p.y << ')'; return out; }
};

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 dist(point a, line b)
{
    if (dot(a - b.p, b.v) < 0 || dot(a - b.p - b.v, b.v * -1) < 0)
        return min(dist(a, b.p), dist(a, b.p + b.v));
    return fabs(cross(a - b.p, b.v)) / dist(point(), b.v);
}

inline bool check(vector<point> &s, point &p)
{
    point temp = s.back(); s.pop_back();
    if (cross(temp - s.back(), p - temp) < 1e-8)
        return false;
    s.push_back(temp); return true;
}

vector<point> convex_hull(int n, point p[], bool flag = false)
{
    vector<point> q;
    sort(p + 1, p + n + 1);
    if (flag) reverse(p + 1, p + n + 1);
    for (int i = 1; i <= n; ++i)
    {
        while ((int)q.size() > 1 && !check(q, p[i]));
        q.push_back(p[i]);
    }
    int temp = q.size();
    for (int i = n - 1; i >= 1; --i)
    {
        while ((int)q.size() > temp && !check(q, p[i]));
        q.push_back(p[i]);
    }
    return q;
}

int n, m;
point p[10005], q[10005];

double solve(vector<point> p, vector<point> q)
{
    static line l1[10005], l2[10005];
    int n = p.size() - 1, m = q.size() - 1;
    for (int i = 0; i < n; ++i)
        l1[i] = line(p[i], p[i + 1] - p[i]);
    for (int i = 0; i < m; ++i)
        l2[i] = line(q[i], q[i + 1] - q[i]);
    double re = 1e20;
    for (int i = 0, j = 0; i < n; ++i)
    {
        while (cross(l1[i].v, l2[j].v) > 0) j = (j + 1) % m;
        re = min(re, dist(p[i], l2[j]));
        re = min(re, dist(p[i + 1], l2[j]));
        re = min(re, dist(q[j], l1[i]));
        re = min(re, dist(q[j + 1], l1[i]));
    }
    return re;
}

int main()
{
    while (cin >> n >> m, n)
    {
        for (int i = 1; i <= n; ++i)
            scanf("%lf%lf", &p[i].x, &p[i].y);
        for (int i = 1; i <= m; ++i)
            scanf("%lf%lf", &q[i].x, &q[i].y);
        printf("%.5lf\n", min(solve(convex_hull(n, p), convex_hull(m, q, true)),
                              solve(convex_hull(m, q), convex_hull(n, p, true))));
    }
    return 0;
}