Chaos Slover 补档计划 - 计算几何(2 凸包、面积问题)

2015.12.04 12:51 Fri| 18 visits oi_2016| ChaosSlover补档计划| Text

POJ1113 Wall

裸题。求凸包周长,最后输出答案时加上 2πl。

 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
#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) > 0; }
    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(deque<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;
}

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

int n, m;
double ans;
point p[1005];
deque<point> s;

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> p[i];
    s = convex_hull(n, p);
    for (int i = 1; i < (int)s.size(); ++i)
        ans += dist(s[i], s[i - 1]);
    cout << fixed << setprecision(0) << ans + 2 * pi * m << endl;
    return 0;
}

POJ1228 Grandpa's Estate

判断一个凸包是否稳定(具体题意网上有)。

于是这一眼就能够看出来是一道卡精度的好题,然而只要注意到 n=1 和共线的两种情况,应该就离 AC 不远了。

 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
#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) > 0; }
    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(deque<point> &s, point &p)
{
    point temp = s.back(); s.pop_back();
    if (cross(temp - s.back(), p - temp) > 0)
        return false;
    s.push_back(temp); return true;
}

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

int test, n;
point p[1005];

int main()
{
    ios::sync_with_stdio(false);
    cin >> test;
    while (test--)
    {
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> p[i];
        if (n == 1) { cout << "NO" << endl; continue; }
        deque<point> d = convex_hull(n, p);
        int vis = 0;
        for (int i = 2; i < (int)d.size(); i += 2)
        {
            ++vis;
            if (cross(d[i] - d[i - 1], d[i - 1] - d[i - 2]) > 1e-8)
                { cout << "NO" << endl; goto end; }
            while (i + 1 < (int)d.size() &&
                cross(d[i + 1] - d[i], d[i] - d[i - 1]) < 1e-8) ++i;
        }
        if (vis == 1) cout << "NO" << endl;
        else cout << "YES" << endl;
        end: ;
    }
    return 0;
}

POJ3348 Cows

求凸包面积 / 50。

 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
#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) > 0; }
    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(deque<point> &s, point &p)
{
    point temp = s.back(); s.pop_back();
    if (cross(temp - s.back(), p - temp) > 0)
        return false;
    s.push_back(temp); return true;
}

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

int n; double ans;
point p[1005];

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> p[i];
    deque<point> d = convex_hull(n, p);
    for (int i = 1; i < (int)d.size(); ++i)
        ans -= cross(d[i - 1], d[i]);
    cout << int(ans / 100) << endl;
    return 0;
}

POJ1654 Area

求多边形的面积。用叉积扫一圈就好了。

 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
#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) > 0; }
    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 test;
char str[1000005];

int main()
{
    cin >> test;
    while (test--)
    {
        scanf("%s", str);
        int len = strlen(str);
        point p, np;
        double ans = 0;
        for (int i = 0; i < len - 1; ++i)
        {
            if (str[i] == '1' || str[i] == '4' || str[i] == '7') --np.x;
            if (str[i] == '3' || str[i] == '6' || str[i] == '9') ++np.x;
            if (str[i] == '1' || str[i] == '2' || str[i] == '3') --np.y;
            if (str[i] == '7' || str[i] == '8' || str[i] == '9') ++np.y;
            ans += cross(p, np); p = np;
        }
        long long t = fabs(ans) + 0.1;
        printf("%lld", t >> 1);
        if (t & 1) printf(".5");
        puts("");
    }
    return 0;
}

POJ1265 Area

求多边形内点数、边上点数和面积。

Pick 定理:面积 = 内部点数 + 边上点数 / 2 - 1。

求边上点数的时候需要注意 abs 函数的参数中不能出现负数。

 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) > 0; }
    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 gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}

int test, n;
char str[1000005];

int main()
{
    cin >> test;
    for (int t = 1; t <= test; ++t)
    {
        cin >> n;
        point p, np;
        int b = 0; double s = 0;
        for (int x, y, i = 1; i <= n; ++i)
        {
            cin >> x >> y;
            b += gcd(abs(x), abs(y));
            np = np + point(x, y);
            s += cross(np, p); p = np;
        }
        s = fabs(s) / 2;
        printf("Scenario #%d:\n%d %d %.1f\n\n", t, int(s - b * 0.5 + 1), b, s);
    }
    return 0;
}

POJ2954 Triangle

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

struct point
{
    int x, y;
    point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
    friend double cross(point a, point b) { return a.x * b.y - a.y * b.x; }
};

int gcd(int a, int b)
{
    if (b == 0) return abs(a);
    return gcd(abs(b), abs(a) % abs(b));
}

int main()
{
    int a, b, c, d, e, f;
    while (cin >> a >> b >> c >> d >> e >> f, a || b || c || d || e || f)
    {
        double area = cross(point(c - a, d - b), point(e - a, f - b)) / 2;
        double p = gcd(c - a, d - b) + gcd(e - a, f - b) + gcd(e - c, f - d);
        cout << fixed << setprecision(0) << fabs(area) - p / 2 + 1 << endl;
    }
    return 0;
}

POJ3335&3130&1474 Rotating Scoreboard

我以前的模板有多渣?要多渣有多渣。

模板中求半平面交如果包含边界,onleft 右面的常数取 1e-8,否则取 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
76
#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)); }
};

deque<pair<line, point> > 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.front().first))
        q.pop_back();
    q.front().second = intersection(q.front().first, q.back().first);
    return q;
}

int test, n;
point p[105]; line l[105];

int main()
{
    cin >> test;
    while (test--)
    {
        cin >> n;
        for (int i = n; i >= 1; --i) cin >> p[i];
        for (int i = 1; i < n; ++i) l[i] = line(p[i], p[i + 1] - p[i]);
        l[n] = line(p[n], p[1] - p[n]);
        deque<pair<line, point> > d = half_plane_intersection(n, l);
        if (d.size() <= 2) puts("NO");
        else puts("YES");
    }
    return 0;
}

POJ1279&2451 Art Gallery

求多边形的核的面积。

POJ2451 这个题的数据范围比较大(其实也并不是很大)。然后交代码不停不停地 TLE,吓傻我了。把所有传结构体都改成了传指针,还 TLE,吓傻我了,差点就去手写 deque 了呢。然后发现交 C++ 就过了,而且并不慢,直接在函数里传结构体的写法还反而更快一点(什么鬼,我真的不知道我都干了些什么)。

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

deque<pair<line, point> > 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.front().first))
        q.pop_back();
    q.front().second = intersection(q.front().first, q.back().first);
    return q;
}

int test, n;
point p[1505]; line l[1505];

int main()
{
    cin >> test;
    while (test--)
    {
        cin >> n;
        for (int i = n; i; --i) cin >> p[i];
        for (int i = 1; i < n; ++i) l[i] = line(p[i], p[i + 1] - p[i]);
        l[n] = line(p[n], p[1] - p[n]);
        deque<pair<line, point> > d = half_plane_intersection(n, l);
        double ans = 0;
        for (int i = 1; i < (int)d.size(); ++i)
            ans += cross(d[i - 1].second, d[i].second);
        ans += cross(d.back().second, d.front().second);
        cout << fixed << setprecision(2) << ans / 2 << endl;
    }
    return 0;
}

POJ3525 Most Distant Point from the Sea

这个故事告诉我们,模板是不能随便更改的……

在删除直线的时候,要先删队尾,再删队头。

如图所示,插入 L3 时显然要删掉 L2,保留 L1,这时删除的顺序就会引起问题了。

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

deque<pair<line, point> > 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);
    return q;
}

line move(line &l, double d)
{
    point t = rotate(l.v, pi / 2);
    return line(l.p + t * (d / dist(point(), t)), l.v);
}

point p[105];
line l[105], c[105];
int n;

int main()
{
    ios::sync_with_stdio(false);
    while (cin >> n, n)
    {
        for (int i = 1; i <= n; ++i)
            cin >> p[i];
        for (int i = 1; i < n; ++i)
            l[i] = line(p[i], p[i + 1] - p[i]);
        l[n] = line(p[n], p[1] - p[n]);
        double tl = 0, tr = 10000, ans = 0;
        while (tl + 1e-7 < tr)
        {
            double mid = (tl + tr) / 2;
            for (int i = 1; i <= n; ++i)
                c[i] = move(l[i], mid);
            if (half_plane_intersection(n, c).size() < (int)3)
                tr = mid;
            else ans = mid, tl = mid;
        }
        cout << fixed << setprecision(6) << ans << endl;
    }
    return 0;
}

POJ3384 Feng Shui

听说这道题最后有可能求出来奇怪的半平面交。

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

deque<pair<line, point> > 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);
    return q;
}

line move(line &l, double d)
{
    point t = rotate(l.v, pi / 2);
    return line(l.p + t * (d / dist(point(), t)), l.v);
}

line l[105];
point p[105];
int n, r;

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> r;
    for (int i = n; i >= 1; --i)
        cin >> p[i];
    for (int i = 1; i < n; ++i)
        l[i] = line(p[i], p[i + 1] - p[i]);
    l[n] = line(p[n], p[1] - p[n]);
    for (int i = 1; i <= n; ++i)
        l[i] = move(l[i], r);
    deque<pair<line, point> > q = half_plane_intersection(n, l);
    int s = q.size(), ans1 = 0, ans2 = 0;
    double maxd = -10;
    for (int i = 0; i < s; ++i)
        for (int j = i + 1; j < s; ++j)
            if (dist(q[i].second, q[j].second) / 2 > maxd)
                maxd = dist(q[i].second, q[j].second) / 2,
                ans1 = i, ans2 = j;
    cout << fixed << setprecision(10) <<
            q[ans1].second.x << ' ' << q[ans1].second.y << ' ' <<
            q[ans2].second.x << ' ' << q[ans2].second.y << endl;
    return 0;
}

POJ1755&BZOJ3800 Triathlon

线性规划转化为半平面交求解。

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

#define S 10000
#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)); }
};

deque<pair<line, point> > 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);
    return q;
}

int n;
double v[105], u[105], w[105];
line l[105];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> u[i] >> w[i];
    for (int i = 1; i <= n; i++)
    {
        bool flag = true;
        int tot = 0;
        for (int j = 1; j <= n; j++)
        {
            if (i == j) continue;
            if (v[i] <= v[j] && u[i] <= u[j] && w[i] <= w[j])
            { flag = false; break; }
            if (v[i] >= v[j] && u[i] >= u[j] && w[i] >= w[j]) continue;
            double a = (S / v[j] - S / w[j]) - (S / v[i] - S / w[i]),
                   b = (S / u[j] - S / w[j]) - (S / u[i] - S / w[i]),
                   c = S / w[j] - S / w[i];
            l[++tot] = line(fabs(a) > fabs(b) ?
                point(-c / a, 0) : point(0, -c / b), point(b, -a));
        }
        if (flag)
        {
            l[++tot] = line(point(0, 0), point(0, -1));
            l[++tot] = line(point(0, 0), point(1, 0));
            l[++tot] = line(point(0, 1), point(-1, 1));
            if(half_plane_intersection(tot, l).size() <= 2) flag = false;
        }
        puts(flag ? "Yes" : "No");
    }
    return 0;
}