C 计算几何

题意

输入一个手的点序列（顺时针 or 逆时针），问你该图像的手性（属于左手 or 属于右手）

思路1: 找特征位置

  1. 手的底部（长度为 9），尾指外侧（长度为 8），拇指外侧（长度为 6）。
  2. 我们先定位手的底部 $L_a$ 和尾指外侧 $L_b$ $(L_i 表示线段)$，它们的长度分别为 9 和 8。
  3. 通过长度定位完成后，我们求出 $L_a$ 和 $L_b$ 的交点 $P$，并将点序列按 $P$ 平移到原点。现在平移问题解决了，我们需要解决旋转问题。我们将 $L_a$ 通过旋转变换，旋转至与 $x$ 轴重合。那么整个图的平移旋转问题都解决了。
  4. 我们定位平移，旋转后的拇指外侧 $L_c$，它的长度为 6，取其上端点 $Q$。
  5. 如果 $Q$ 属于 2，4 象限，那么为右手，反之为左手。

拓展1

以后遇到手性的题目，首先找图的特征，然后归一化点序列（旋转，平移），通过判断某些特征点（特征边）所在的位置，就可以判断该图像的手性。

代码1

#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
const double EPS = 1e-3;

int dcmp(double x) {
    if (fabs(x) <= EPS) return 0;
    if (x < -EPS) return -1;
    return 1;
}

struct Point {
    double x, y;

    Point() : x(0), y(0) { }
    Point(double x, double y) : x(x), y(y) { }

    double dis(const Point& p) const {
        return hypot(x - p.x, y - p.y);
    }

    Point rotate(double degree) const {
        double c = cos(degree), s = sin(degree);
        return Point {x * c - y * s, x * s + y * c};
    }

    bool operator < (const Point& p) const {
        return x != p.x ? x < p.x : y < p.y;
    }

    bool operator == (const Point& p) const {
        return x == p.x && y == p.y;
    }

    Point operator - (const Point& p) const {
        return {x - p.x, y - p.y};
    }
};

using Vector = Point;

struct Line {
    Point x, y;

    Line() { ; }
    Line(Point x, Point y) : x(x), y(y) { }
    
    Point common(const Line& l) const {
        for (auto& u: {x, y})
            for (auto& v: {l.x, l.y})
                if (u == v) 
                    return u;

        const auto inf = 1e9;
        return Point(inf, inf);
    }

    Vector vector() const {
        return x - y;
    }
};

Point p[20];

Line find(Point* p, double dis) {
    for (int i = 0; i < 20; ++i) {
        if (fabsl(p[i].dis(p[(i + 1) % 20]) - dis) < EPS) {
            return Line(p[i], p[(i + 1) % 20]); 
        }
    }
    return Line();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        for (int i = 0; i < 20; ++i) 
            cin >> p[i].x >> p[i].y;
        
        Line a = find(p, 9);
        Line b = find(p, 8);
        Point o = a.common(b);

        for (int i = 0; i < 20; ++i) 
            p[i] = p[i] - o;

        Vector v = a.vector();
        if (v.x != 0) {
            auto degree = -atan(v.y / v.x);
            for (int i = 0; i < 20; ++i) 
                p[i] = p[i].rotate(degree);
        }
        
        Line c = find(p, 6);
        if (dcmp(c.x.y) == 0)               swap(c.x, c.y);
        if (dcmp(c.x.x * c.x.y) == -1)      cout << "right\n";
        else                                cout << "left\n";
    }
    return 0;
}

思路2: 归一化点序列为逆时针方向

  1. 如果是右手，那么拇指外侧的边 $L_a$ 的下一条边一定是 手掌底部的边 $L_b$
  2. 反之，则是左手,由于手的形状不是凸包，所以我们需要找到凸的位置判断方向，并进行归一化。如果不选择凸的位置进行方向判断则会 wrong answer 到哭。判断方向可以利用叉积进行判断。

拓展2

对于任意的点序列，我们可以利用凸包算法，算出凸包，凸包总是逆时针的 (Graham算法)，因此可以归一化成凸包进行判断。

代码2

#include <bits/stdc++.h>
using namespace std;

const double PI = acos(-1);
const double EPS = 1e-3;
struct Point;
using Vector = Point;

int dcmp(double x) {
    if (fabs(x) <= EPS) return 0;
    if (x < -EPS) return -1;
    return 1;
}

struct Point {
    double x, y;

    Point() : x(0), y(0) { }
    Point(double x, double y) : x(x), y(y) { }

    double dis(const Point& p) const {
        return hypot(x - p.x, y - p.y);
    }

    Vector operator - (const Point& p) const {
        return {x - p.x, y - p.y};
    }

    double cross(const Vector& p) const {
        return x * p.y - p.x * y;
    }
};

Point p[20];
vector<double> edge;

void normalize(Point *p) {

    int idx = 0;
    for (int i = 0; i < 20; ++i) {
        if (dcmp(p[i].dis(p[(i + 1) % 20]) - 6) == 0) {
            idx = i;
            break;
        }
    }

    Point q[20];
    for (int i = 0; i < 20; ++i) {
        q[i] = p[(i + idx) % 20];
    }

    for (int i = 0; i < 20; ++i) {
        p[i] = q[i];
    } 

    if (dcmp((p[1] - p[0]).cross(p[2] - p[1])) < 0) {
        for (int i = 0, j = 19; i < j; ++i, --j) {
            swap(p[i], p[j]);
        }
    }

    edge.clear();
    for (int i = 0; i < 20; ++i) {
        edge.emplace_back(p[i].dis(p[(i + 1) % 20]));
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t;
    cin >> t;
    while(t--) {
        for (int i = 0; i < 20; ++i) {
            cin >> p[i].x >> p[i].y;
        }
        
        normalize(p);

        int u = find_if(edge.begin(), edge.end(), [](double x) {
            return dcmp(x - 6) == 0;
        }) - edge.begin();

        if (dcmp(edge[(u + 1) % 20] - 9) == 0)  cout << "right\n";
        else                                    cout << "left\n";
    }
    return 0;
}

思路3

上面的思路其实都没啥必要，只有思路2有点价值。但是思路2的处理并不明智，因为我们可以使用格林公式判断顺逆，从而判断手性

代码3

#include <bits/stdc++.h>

using namespace std;
const double EPS = 1e-5;
const int N = 20;

int dcmp(double x) {
    if (fabs(x) <= EPS) return 0;
    if (fabs(x) < -EPS) return -1;
    return 1;
}

struct Point {
    double x, y;

    double dis(const Point& p) const {
        return hypot(x - p.x, y - p.y);
    }
} p[N];

int clockwise(Point* p, int n) {
    double temp = 0;
    for (int i = 0; i < n; ++i)
        temp += -0.5 * (p[(i + 1) % n].y + p[i].y) * (p[(i + 1) % n].x - p[i].x);
    return temp < 0 ? -1 : 1;
}

int find(Point *p, int n, double len) {
    for (int i = 0; i < n; ++i) {
        if (dcmp(p[i].dis(p[(i + 1) % n]) - len) == 0) return i;
    }
    return -1;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        for (int i = 0; i < 20; ++i)
            scanf("%lf%lf", &p[i].x, &p[i].y);

        if (clockwise(p, 20) == 1) reverse(p, p + 20);
        int u = find(p, 20, 9), v = find(p, 20, 6);
        if ((v + 1) % 20 == u) puts("left");
        else puts("right");
    }
    return 0;
}