极角序叉积做法70pts
查看原帖
极角序叉积做法70pts
833124
BIOS楼主2023/10/18 22:50
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
const double eps = 1e-10;
#define x first
#define y second
typedef pair<int, int> PII;
PII p, q[3];
PII operator-(PII a, PII b)
{
    return {a.x - b.x, a.y - b.y};
}
double cross(PII a, PII b)
{
    return a.x * b.y - a.y * b.x;
}
double area(PII a, PII b, PII c)
{
    return cross(b - a, c - a);
}
int dcmp(double x, double y)
{
    if (fabs(x - y) < eps)
        return 0;
    return x < y ? -1 : 1;
}
int sign(double x)
{
    if (fabs(x) < eps)
        return 0;
    return x < 0 ? -1 : 1;
}
struct Line
{
    PII st, ed;
} line[3], a, b, c;
bool st[101][101];
double tmp[3];
double dot(PII a, PII b)
{
    return a.x * b.x + a.y * b.y;
}
double get_len(PII a)
{
    return sqrt(dot(a, a));
}
double get_angle(Line a)
{
    return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x);
}
bool cmp(Line a, Line b)
{
    double A = get_angle(a), B = get_angle(b);
    if (!dcmp(A, B))
        return area(a.st, a.ed, b.ed) <= 0;
    return A < B;
}
int main()
{
    scanf("(%d,%d)\n", &q[0].x, &q[0].y);
    scanf("(%d,%d)\n", &q[1].x, &q[1].y);
    scanf("(%d,%d)\n", &q[2].x, &q[2].y);
    for (int i = 0; i < 3; i++)
        line[i] = {q[i], q[(i + 1) % 3]};
    sort(line, line + 3, cmp), a = line[0], b = line[1], c = line[2];
    scanf("(%d,%d)\n", &p.x, &p.y);
    st[q[0].x][q[0].y] = st[q[1].x][q[1].y] = st[q[2].x][q[2].y] = true;
    if (st[p.x][p.y])
        return cout << 4 << endl, 0;
    tmp[0] = area(a.st, a.ed, p);
    tmp[1] = area(b.st, b.ed, p);
    tmp[2] = area(c.st, c.ed, p);
    for (int i = 0; i < 3; i++)
        if (sign(tmp[i]) < 0)
            cout << 2 << endl, exit(0);
    for (int i = 0; i < 3; i++)
        if (!sign(tmp[i]))
            cout << 3 << endl, exit(0);
    cout << 1 << endl;
}

我是这么想的,极角序排列以后顺次连接,获得的就是一个逆时针的向量环,然后求一遍叉积,如果全正则在里,如果有0则在边上,如果有负数说明在外面,如果有重合点就是4。 然后错误的三个点里,一个是实际2输出3,两个实际1输出2,没感觉哪里出锅(?)

2023/10/18 22:50
加载中...