QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#610860 | #5479. Traveling Salesperson in an Island | quanlt206 | WA | 1ms | 4008kb | C++14 | 6.7kb | 2024-10-04 17:48:28 | 2024-10-04 17:48:28 |
Judging History
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'