QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#610860#5479. Traveling Salesperson in an Islandquanlt206WA 1ms4008kbC++146.7kb2024-10-04 17:48:282024-10-04 17:48:28

Judging History

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

  • [2024-10-04 17:48:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4008kb
  • [2024-10-04 17:48:28]
  • 提交

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() {
    #ifndef ONLINE_JUDGE
    freopen("tsp.inp", "r", stdin);
    freopen("tsp.out", "w", stdout);
    #endif // ONLINE_JUDGE
    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();
//    cout<<segment_inside(a[1], b[4]);
//    exit(0);
//    exit(0);
////    exit(0);
//    for (int i = 1; i <= m; i++) cout<<b[i].x<<" "<<b[i].y<<"\n";
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++) cout<<i<<" "<<j<<" "<<segment_inside(a[i], b[j])<<"\n";
//    exit(0);
    build_graph();
    floyd();
//    cout<<w[9][10]<<"\n";
    long double res = 0;
    for (int i = 1; i < m; i++) {
        res+=w[i + n][i + 1 + n];
//        cout<<fixed<<setprecision(10)<<w[i + n][i + 1 + n]<<"\n";
    }
    res+=w[m + n][1 + n];
    cout<<fixed<<setprecision(14)<<res;
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3972kb

input:

4 4
0 0
2 0
2 2
0 2
1 0
1 2
2 1
0 1

output:

5.65685424949238

result:

ok found '5.6568542', expected '5.6568542', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4008kb

input:

8 2
0 0
4 0
4 4
0 4
0 3
3 3
3 1
0 1
0 0
0 4

output:

16.64911064067352

result:

ok found '16.6491106', expected '16.6491106', error '0.0000000'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3956kb

input:

4 4
0 0
2 0
2 2
0 2
1 0
2 1
1 2
0 1

output:

6.82842712474619

result:

wrong answer 1st numbers differ - expected: '5.6568542', found: '6.8284271', error = '0.2071068'