Chaos Slover 补档计划 - 计算几何(1 计算几何基础)

2015.12.04 08:03 Fri| 20 visits oi_2016| ChaosSlover补档计划| Text

各种背模板 + 各种乱搞 + 各种卡精度 = 绝大多数选手都不会(CCF)。

POJ2318&2398 TOYS

n 条线把矩形划分成了 n+1 个区域。给出 m 个点,问各个区域中分别有多少点。

二分查找每一个点所在的区域即可。

POJ2398 中的挡板没有排序,需要注意。

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

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

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

line ln[5005];
double x1, x2, y1, y2;
int n, m, cnt[5005];
point p;

inline long long read()
{
    long long 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)
    {
        cin >> m >> x1 >> y1 >> x2 >> y2;
        ln[0] = line(point(x1, y2), point(0, 1));
        for (int i = 1; i <= n; ++i)
        {
            long long a = read(), b = read();
            ln[i] = line(point(b, y2), point(a, y1) - point(b, y2));
        }
        memset(cnt, 0, sizeof cnt);
        for (int i = 0; i < m; ++i)
        {
            int l = 0, r = n, ans = 0;
            p.x = read(); p.y = read();
            while (l <= r)
            {
                int mid = (l + r) >> 1;
                if (onleft(p, ln[mid])) r = mid - 1;
                else ans = mid, l = mid + 1;
            }
            ++cnt[ans];
        }
        for (int i = 0; i <= n; ++i)
            printf("%d: %d\n", i, cnt[i]);
        puts("");
    }
    return 0;
}

POJ3304 Segments

给出平面上的 N 条线段,判断是否存在某一条直线使得所有线段在直线上的投影存在公共交点。

我们知道,如果存在这样的一条直线,那么从公共交点作直线的垂线,它与所有的线段相交。反之如果存在一条直线与所有线段相交,我们可以知道存在符合题意的一条直线。

现在问题就转化成了是否有一条直线与所有线段相交。我们知道如果存在这样的一条直线,必然能够使其与这些线段的端点中的至少两个相交。那么枚举每两个端点,作直线,判断是否与其他线段全部相交。

注意这道题中,距离小于 1e-8 的点算作重合。在枚举端点的时候也需要判断一下。

 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 sqr(x) ((x) * (x))
#define dcmp(x) (fabs(x) < 1e-8)

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, n;
point p[205];
line l[105];

bool check(int i, int j, int k)
{
    line t = line(p[i], p[j] - p[i]);
    point t2 = intersection(t, l[k]);
    if ((t2.x < l[k].p.x - 1e-8 && t2.x < (l[k].p + l[k].v).x - 1e-8) ||
        (t2.x > l[k].p.x + 1e-8 && t2.x > (l[k].p + l[k].v).x + 1e-8) ||
        (t2.y < l[k].p.y - 1e-8 && t2.y < (l[k].p + l[k].v).y - 1e-8) ||
        (t2.y > l[k].p.y + 1e-8 && t2.y > (l[k].p + l[k].v).y + 1e-8))
        return false;
    return true;
}

int main()
{
    cin >> test;
    while (test--)
    {
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> p[i * 2 - 1] >> p[i * 2],
            l[i] = line(p[i * 2 - 1], p[i * 2] - p[i * 2 - 1]);
        for (int i = 1; i <= n * 2; ++i)
            for (int j = i + 1; j <= n * 2; ++j)
                if (dist(p[i], p[j]) > 1e-8)
                    for (int k = 1; k <= n + 1; ++k)
                        if (k == n + 1) { puts("Yes!"); goto end; }
                        else if (!check(i, j, k)) break;
        puts("No!");
        end: ;
    }
    return 0;
}

POJ1269 Intersecting Lines

判断直线间的位置关系,需要在代码中多加几个判断。

为了保证极角相等,不出现反向平行的情况,最开始可以给点简单排一个序,从而简化讨论。

 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
#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 << "POINT " << 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;
point p1, p2, p3, p4;
line l1, l2;

int main()
{
    cin >> test;
    puts("INTERSECTING LINES OUTPUT");
    cout << fixed << setprecision(2);
    while (test--)
    {
        cin >> p1 >> p2 >> p3 >> p4;
        if (p2 < p1) swap(p1, p2);
        if (p4 < p3) swap(p3, p4);
        if (p3 < p1) swap(p1, p3), swap(p2, p4);
        l1 = line(p1, p2 - p1);
        l2 = line(p3, p4 - p3);
        if (!dcmp(l1.t - l2.t))
            cout << intersection(l1, l2) << '\n';
        else if (dcmp(line(p1, p3 - p1).t - l2.t))
            puts("LINE");
        else puts("NONE");
    }
    puts("END OF OUTPUT");
    return 0;
}

POJ2826 An Easy Problem?!

各种乱七八糟的判断。

 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.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 t;
point a, b, c, d;
line l1, l2;

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y, &c.x, &c.y, &d.x, &d.y);
        if (a.y < b.y) swap(a, b);
        if (c.y < d.y) swap(c, d);
        if (a.y < c.y) swap(a, c), swap(b, d);
        l1 = line(a, b - a);
        l2 = line(c, d - c);
        point p = intersection(l1, l2);
        if ((p.x < a.x - 1e-8 && p.x < b.x - 1e-8) || (p.x > a.x + 1e-8 && p.x > b.x + 1e-8)
         || (p.x < c.x - 1e-8 && p.x < d.x - 1e-8) || (p.x > c.x + 1e-8 && p.x > d.x + 1e-8))
            { puts("0.00"); continue; }
        if ((p.y < a.y - 1e-8 && p.y < b.y - 1e-8) || (p.y > a.y + 1e-8 && p.y > b.y + 1e-8)
         || (p.y < c.y - 1e-8 && p.y < d.y - 1e-8) || (p.y > c.y + 1e-8 && p.y > d.y + 1e-8))
            { puts("0.00"); continue; }
        if ((onleft(c, l1) && c.x < a.x + 1e-8) || (!onleft(c, l1) && c.x > a.x - 1e-8))
            { puts("0.00"); continue; }
        if (a.y <= d.y + 1e-8 || c.y <= p.y + 1e-8)
            { puts("0.00"); continue; }
        point t = intersection(l1, line(c, point(1, 0)));
        double ans = cross(t - p, l2.p - p) / 2;
        if (isnan(ans) || isinf(ans)) { puts("0.00"); continue; }
        printf("%.2f\n", fabs(ans) + 1e-8);
    }
    return 0;
}