[数据结构与算法]牛客竞赛计算几何专题班二维基础

?

B.Mr. Main and Windmills

代码：

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<bits/stdc++.h>
#define db double
using namespace std;
const int maxn = 1e3 + 10;
const int inf = 1e9;
double nx[maxn], ny[maxn];
int sx, sy, tx, ty;
int N, M;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) :x(x), y(y) {}
};

vector<Point>vec[maxn];
vector<Point>vec1[maxn];

typedef Point Vector;

Vector operator + (Vector A, Vector B) {
    return Vector(A.x + B.x, A.y + B.y);
}

Vector operator - (Point A, Point B) {
    return Vector(A.x - B.x, A.y - B.y);
}

Vector operator * (Vector A, double p) {
    return Vector(A.x * p, A.y * p);
}

Vector operator / (Vector A, double p) {
    return Vector(A.x / p, A.y / p);
}

struct Line {//直线定义
    Point v, p;
    Line(Point v, Point p) :v(v), p(p) {}
    Point point(double t) {//返回点P = v + (p - v)*t
        return v + (p - v) * t;
    }
};

double Cross(Vector A, Vector B) {
    return A.x * B.y - A.y * B.x;
}

Point GetLineIntersection(Point P, Vector v, Point Q, Vector w) {
    Vector u = P - Q;
    double t = Cross(w, u) / Cross(v, w);
    return P + v * t;
}

double Dot(Vector A, Vector B) {
    return A.x * B.x + A.y * B.y;
}

const double eps = 1e-15;

int dcmp(double x, double y) {
    if (fabs(x - y) < eps)
        return 0;
    if (x > y)
        return 1;
    return -1;
}

int sgn(double x) {
    if (fabs(x) < eps)
        return 0;
    if (x < 0)
        return -1;
    return 1;
}

bool OnSegment(Point p, Point a1, Point a2) {
    return  sgn(Dot(a1 - p, a2 - p)) < 0 ;//&& sgn(Cross(a1 - p, a2 - p)) == 0;
}

bool up(Point a, Point b) {
    return a.x > b.x;
}

bool low(Point a, Point b) {
    return a.x < b.x;
}


int main() {
    cin >> N >> M;
    cin >> sx >> sy >> tx >> ty;
    Point S(sx, sy);
    Point T(tx, ty);
    Point P[maxn];
    Line car(S, T);
    for (int i = 1; i <= N; i++) {
        cin >> P[i].x >> P[i].y;
    }
    int f = 0;
    if (sx > tx)f = 1;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            Line feng(P[i], P[j]);
            if (i == j)continue;
            if (Cross(S - T, P[i] - P[j]) == 0)continue;
            Point d = GetLineIntersection(S, T - S, P[i], P[j] - P[i]);
            if (OnSegment(d, S, T))vec[i].push_back(d);
        }
        int len = vec[i].size();
        if (f)sort(vec[i].begin(), vec[i].end(), up);
        else sort(vec[i].begin(), vec[i].end(), low);

    }
    while (M--) {
        int p, k; cin >> p >> k;
        int tt=vec[p].size();
        if (tt < k)cout << -1 << endl;
        else printf("%.10f %.10f\n", vec[p][k - 1].x, vec[p][k - 1].y);
    }
    return 0;
}

D.Operation Love

题意：

在二维坐标图给出一个手掌状图形，判断该图形是左手还是右手。

题解：

枚举所有线段，通过线段长度找到A，B，C三个点，若$BC$在$AB$的逆时针方向为左手，否则为右手。

代码：

t B) { return Vector(A.x - B.x, A.y - B.y); }
Vector operator * (Vector A, double p) { return Vector(A.x * p, A.y * p); }
Vector operator / (Vector A, double p) { return Vector(A.x / p, A.y / p); }
bool operator < (const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
bool operator ==(const Point& a, const Point& b) { return !sgn(a.x - b.x) && !sgn(a.y - b.y); }

//点积,可用于判断角度
double Dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; }

//叉积
double Cross(Vector A, Vector B) { return A.x * B.y - B.x * A.y; }

//模长
double Length(Vector A) { return sqrt(Dot(A, A)); }

//判断 bc 是不是在 ab 的逆时针方向,向量夹角<90
bool ToLeftTest(Point a, Point b, Point c) { return Cross(b - a, c - b) > 0; }


int T;

int main() {
    ios::sync_with_stdio(0);
    cin >> T;
    while (T--) {
        Point p[30], P1, P2, P3, P4;
        for (int i = 1; i <= 20; i++)cin >> p[i].x >> p[i].y;
        p[21] = p[1], p[22] = p[2];
        p[0] = p[20];
        for (int i = 1; i <= 20; i++) {
            double L = Length(p[i + 1] - p[i]);
            if (L - 8.5 > eps) {//找到线段ＡＢ
               // P1 = p[i], P2 = p[i + 1];
                double L1 = Length(p[i - 1] - p[i]), L2 = Length(p[i + 2] - p[i + 1]);
                //根据长度区分C点（P3）
                if (L2 - L1 > eps)P1 = p[i], P2 = p[i + 1], P3 = p[i - 1];
                if (L1 - L2 > eps)P1 = p[i + 1], P2 = p[i], P3 = p[i + 2];
                break;
            }
        }
        if (!ToLeftTest(P2, P1, P3))cout << "right\n";
        else cout << "left\n";
    }
	return 0;
}

?