QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#262867#5479. Traveling Salesperson in an Islandxaphoenix#WA 1ms3776kbC++175.9kb2023-11-24 09:33:162023-11-24 09:33:17

Judging History

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

  • [2023-11-24 09:33:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3776kb
  • [2023-11-24 09:33:16]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define LC k<<1
#define RC k<<1|1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repn(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = (n) - 1; i >= a; i--)
#define pern(i, a, n) for (int i = n; i >= a; i--)

typedef long long LL;
typedef long double LD;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef pair<double, double> PDD;
typedef pair<ull, ull> PUU;
typedef pair<LL, LL> PLL;

const int N = 210;
const int M = 1100000;
const int mod = 1e9+7;
const int inf = (int)1e9;
const LL INF = 1e18;

mt19937_64 Rand((unsigned long long)new char);
#define rand Rand

int n, m;
const double eps = 1e-5, pi = acos(-1.0);
inline int dcmp(double x) {
    return (x > eps) - (x < -eps);
}
double dis[N][N];
struct Point {
    double x, y;
    int id;
    double d;
    Point (double x = 0 , double y = 0) : x(x) , y(y) {}
    void input() {
        cin >> x >> y;
    }
    bool operator < (const Point& R) const {
        if (dcmp(x - R.x) == 0)
            return dcmp(y - R.y) < 0;
        return dcmp(x - R.x) < 0;
    }
    bool operator == (const Point& R) const {
        return dcmp(x - R.x) == 0 && dcmp(y - R.y) == 0;
    }
    Point operator + (const Point& R) const {
        return Point(x + R.x, y + R.y);
    }
    Point operator - (const Point& R) const {
        return Point(x - R.x, y - R.y);
    }
    Point operator * (const double& R) const {
        return Point(x * R, y * R);
    }
    Point operator / (const double& R) const {
        return Point(x / R, y / R);
    }
    double operator ^ (const Point& R) const {
        return x * R.y - y * R.x;
    }
    double operator % (const Point& R) const {
        return x * R.x + y * R.y;
    }
    double len() {
        return sqrt(*this % *this);
    }
    double angle() {
        return atan2(y, x);
    }
}p[N], poly[N];
double Angle(Point A, Point B) {
    return acos((A % B) / A.len() / B.len());
}
Point Rotate(Point A, double rad) {
    double Sin = sin(rad) , Cos = cos(rad);
    return Point(A.x * Cos - A.y * Sin , A.x * Sin + A.y * Cos);
}
Point Normal(Point A) {
    double L = A.len();
    return Point(-A.y / L , A.x / L);
}
Point GetLineIntersection(Point P, Point v, Point Q, Point w) {
    Point u = P - Q;
    double t1 = (w ^ u) / (v ^ w);
    return P + v * t1;
}
double DistancePointToLine(Point P, Point A, Point B) {
    Point v = B - A;
    return (v ^ (P - A)) / v.len();
}
double DistancePointToSegment(Point P, Point A, Point B) {
    if (A == B) return (P - A).len();
    Point v1 = B - A , v2 = P - A , v3 = P - B;
    if (dcmp(v1 % v2) < 0) return v2.len();
    if (dcmp(v1 % v3) > 0) return v3.len();
    return fabs(v1 ^ v2) / v1.len();
}
Point GetLineProjection(Point P, Point A, Point B) {
    Point v = B - A;
    return A + v * (v % (P - A) / (v % v));
}
bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2) {
    double c1 = (a2 - a1) ^ (b1 - a1);
    double c2 = (a2 - a1) ^ (b2 - a1);
    if (dcmp(c1) == 0 && dcmp(c2) == 0) {
        if (a2 < a1) swap(a1 , a2);
        if (b2 < b1) swap(b1 , b2);
        return max(a1 , b1) < min(a2 , b2);
    }
    double c3 = (b2 - b1) ^ (a1 - b1);
    double c4 = (b2 - b1) ^ (a2 - b1);
    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}

bool OnSegment(Point P, Point a1, Point a2) {
    double len = (P - a1).len();
    if (dcmp(len) == 0) return true;
    a1 = a1 - P , a2 = a2 - P;
    return dcmp((a1 ^ a2) / len) == 0 && dcmp(a1 % a2) <= 0;
}
bool SegmentIntersection(Point a1, Point a2, Point b1, Point b2) {
    if (OnSegment(a1, b1, b2)) return true;
    if (OnSegment(a2, b1, b2)) return true;
    if (OnSegment(b1, a1, a2)) return true;
    if (OnSegment(b2, a1, a2)) return true;
    return SegmentProperIntersection(a1, a2, b1, b2);
}
int cmp(Point a, Point b) {
	if (a.id != b.id) return a.id < b.id;
	return a.d < b.d;
}
bool pointInPolygon(Point P , Point *p , int n) {
    for (int i = 0 ; i < n ; ++ i)
        if (OnSegment(P , p[i] , p[i + 1]))
            return 1;
    int res = 0;
    for (int i = 0 ; i < n ; ++ i) {
        Point a = p[i] , b = p[i + 1];
        if (a.y > b.y) swap(a , b);
        if (dcmp((a - P) ^ (b - P)) < 0 && dcmp(a.y - P.y) < 0 && dcmp(b.y - P.y) >= 0)
            res ^= 1;
    }
    return res;
}
int main() {
	IO;
	cin >> n >> m;
	repn(i, 1, n + m) p[i].input();
	rep(i, 0, n) poly[i] = p[i + 1];
	poly[n] = p[1];
	repn(i, n + 1, n + m) {
		repn(j, 1, n) {
			Point x = p[j], y;
			if (j == n) y = p[1];
			else y = p[j + 1];
			if (!(p[i] == y) && OnSegment(p[i], x, y)) {
				p[i].id = j;
				p[i].d = (p[i] - x).len();
				break;
			}
		}
	}
	sort(p + n + 1, p + n + m + 1, cmp);
	repn(i, 1, n + m) repn(j, 1, n + m) {
		dis[i][j] = INF;
		Point x = p[i], y = p[j];
		vector<Point> v;
		v.pb(x), v.pb(y);
		repn(k, 1, n) {
			Point a = p[k], b;
			if (k == n) b = p[1];
			else b = p[k + 1];
			if (SegmentIntersection(x, y, a, b)) {
				Point z = GetLineIntersection(x, y - x, a, b - a);
				v.pb(z);
			}
		}
		sort(all(v));
		int flag = 0;
		rep(i, 1, SZ(v)) {
			if (v[i - 1] == v[i]) continue;
			Point c = (v[i - 1] + v[i]) / 2;
			if (!pointInPolygon(c, poly, n)) {
				flag = 1;
				break;
			}
		}
		if (!flag) dis[i][j] = (p[i] - p[j]).len();
	}
	repn(k, 1, n + m) repn(i, 1, n + m) repn(j, 1, n + m) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
	double ans = 0;
	repn(i, n + 2, n + m) ans += dis[i - 1][i];
	ans += dis[n + m][n + 1];
	cout << fixed << setprecision(15) << ans << "\n";
	return 0;
}

详细

Test #1:

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

input:

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

output:

5.656854249492381

result:

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

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3680kb

input:

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

output:

21.802093085756468

result:

wrong answer 1st numbers differ - expected: '16.6491106', found: '21.8020931', error = '0.3095050'