QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#610856#5479. Traveling Salesperson in an Islandquanlt206Compile Error//C++146.1kb2024-10-04 17:47:502024-10-04 17:47:51

Judging History

你现在查看的是最新测评结果

  • [2024-10-04 17:47:51]
  • 评测
  • [2024-10-04 17:47:50]
  • 提交

answer

#include<bits/stdc++.h>
#define X first
#define Y second
#define Point Vector
#define all(x) begin(x), end(x)

using namespace std;

typedef long long ll;

const int N = 1e3 + 7;
const long double eps = 1e-9;
const long double pi = acos(-1);

template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }

struct Vector {
    long double x, y;
    Vector() {
        x = y = 0;
    }
    Vector(long double x, long double y) : x(x), y(y) {}
    Vector operator - (const Vector& v) const {
        return Vector(x - v.x, y - v.y);
    }
    long double operator * (const Vector& v) const {
        return x * v.x + y * v.y;
    }
    long double operator % (const Vector& v) const {
        return x * v.y - v.x * y;
    }
    bool operator == (const Vector& v) const {
        return abs(x - v.x) < eps && abs(y - v.y) < eps;
    }
    bool operator < (const Vector& v) const {
        return x < v.x || (abs(x - v.x) < eps && y < v.y);
    }
    bool operator >= (const Vector& v) const {
        return x > v.x || (abs(x - v.x) < eps && y >= v.y);
    }
    friend double angle(Vector a, Vector b) {
        return atan2(a%b,a*b);
    }
} a[N], b[N];

int n, m;

bool on_boundary(Point x) {
    a[n + 1] = a[1];
    for (int i = 1; i <= n; i++)
        if ((x - a[i]) % (a[i + 1] - x) == 0 && (x - a[i]) * (x - a[i + 1]) <= 0) {
            return true;
        }
    return false;
}

bool check_inside(Point x) {
//    cout<<x.x<<" "<<x.y<<"\n";
//    cout<<on_boundary(x)<<"\n";
    if (on_boundary(x)) return true;
    a[n + 1] = a[1];
    long double ang = 0;
    for (int i = 1; i <= n; i++) ang+=angle(a[i] - x, a[i + 1] - x);
    return abs(ang - pi * 2) < eps;
}

bool on_side(Point x, Point a, Point b) {
    return (x - a) % (b - x) == 0 && (x - b) * (x - b) <= 0;
}

int cv(long double x) {
    if (abs(x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}

bool check_giao(Point A, Point B, Point C, Point D) {
    if (abs((C - B) % (B - A)) < eps && abs((D - B) % (B - A)) < eps) return false;
    return cv((B - A) % (C - B)) * cv((B - A) % (D - B)) <= 0 && cv((D - C) % (A - D)) * cv((D - C) % (B - D)) <= 0;
}

Vector solveSLE(Vector a, Vector b, Vector c) {
    long double D = a % b;
//    if (D == 0) assert(false);
    return Vector(c % b / D, a % c / D);
}

Point find_intersect(Point A, Point B, Point C, Point D) {
    Vector r = solveSLE(B - A, C - D, C - A);
    return Point(A.x + (B - A).x * r.x, A.y + (B - A).y * r.x);
}

bool check_intersect(Point x, Point y) {
    a[n + 1] = a[1];
    for (int i = 1; i <= n; i++) {
        if (on_side(a[i], x, y) && on_side(a[i + 1], x, y)) {
            if (a[i] == x && a[i + 1] == y) continue;
            if (a[i] == y && a[i + 1] == x) continue;
            return false;
        }
        if (a[i] == x || a[i] == y || a[i + 1] == x || a[i + 1] == y) continue;
        if (check_giao(x, y, a[i], a[i + 1])) {
            Vector tmp = find_intersect(x, y, a[i], a[i + 1]);
            if (!(tmp == x || tmp == y)) return false;
        }
    }
    return true;
}

bool segment_inside(Point a, Point b) {
    Point mid((a.x + b.x) / 2, (a.y + b.y) / 2);
    return check_inside(mid) && check_intersect(a, b);
}


int find_boundary(Point x) {
    a[n + 1] = a[1];
    for (int i = 1; i <= n; i++)
        if ((x - a[i]) % (a[i + 1] - x) == 0 && (x - a[i]) * (a[i + 1] - x) <= 0) return i;
}

long double SQR(long double x) {
    return x * x;
}


long double dist(Point a, Point b) {
    return sqrt(SQR(a.x - b.x) + SQR(a.y - b.y));
}

Point st;

int idxSt = 0, index_boundary[N];

void sort_m_point() {
    st = b[1];
    vector<int> pos;
    for (int i = 1; i <= m; i++) {
        pos.push_back(i);
        index_boundary[i] = find_boundary(b[i]);
    }
    sort(all(pos), [=](int x, int y){
         return index_boundary[x] != index_boundary[y] ? index_boundary[x] < index_boundary[y] : dist(a[index_boundary[x]], b[x]) < dist(a[index_boundary[x]], b[y]);
    });
    vector<Point> new_point;
    for (int i = 1; i <= m; i++) new_point.push_back(b[pos[i - 1]]);
    for (int i = 1; i <= m; i++) b[i] = new_point[i - 1];
    for (int i = 1; i <= m; i++)
        if (st == b[i]) idxSt = i;
}

long double w[N][N];

void build_graph() {
    for (int i = 1; i <= n + m; i++)
        for (int j = 1; j <= n + m; j++) w[i][j] = 1e9;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            if (segment_inside(b[i], b[j])) w[i + n][j + n] = dist(b[i], b[j]); else w[i + n][j + n] = 2e9;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (segment_inside(a[i], a[j])) w[i][j] = dist(a[i], a[j]); else w[i][j] = 1e9;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (segment_inside(a[i], b[j])) w[i][j + n] = dist(a[i], b[j]); else w[i][j + n] = 1e9;
//    cout<<n<<" "<<m<<"\n";
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (segment_inside(b[i], a[j])) w[i + n][j] = dist(b[i], a[j]); else w[i + n][j] = 1e9;
    for (int i = 1; i <= m + n; i++)
        for (int j = i + 1; j <= m + n; j++)
            if (w[i][j] != 1e9 && i != j) {
//                if (i > n) cout<<b[i - n].x<<" "<<b[i - n].y<<" -> "; else cout<<a[i].x<<" "<<a[i].y<<" -> ";
//                if (j > n) cout<<b[j - n].x<<" "<<b[j - n].y<<" -> "; else cout<<a[j].x<<" "<<a[j].y<<" : ";
//                cout<<w[i][j]<<"\n";
            }
}

void floyd() {
    for (int u = 1; u <= n + m; u++)
        for (int v = 1; v <= n + m; v++)
            for (int k = 1; k <= n + m; k++) minimize(w[u][v], w[u][k] + w[k][v]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for (int i = 1; i <= n; i++) cin>>a[i].x>>a[i].y;
    for (int i = 1; i <= m; i++) cin>>b[i].x>>b[i].y;
    sort_m_point(););
    build_graph();
    floyd();
    long double res = 0;
    for (int i = 1; i < m; i++) {
        res+=w[i + n][i + 1 + n];
    }
    res+=w[m + n][1 + n];
    cout<<fixed<<setprecision(14)<<res;
    return 0;
}


详细

answer.code: In function ‘int main()’:
answer.code:194:20: error: expected primary-expression before ‘)’ token
  194 |     sort_m_point(););
      |                    ^
answer.code: In function ‘int find_boundary(Vector)’:
answer.code:123:1: warning: control reaches end of non-void function [-Wreturn-type]
  123 | }
      | ^