QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#102999#3184. Around the TrackPetroTarnavskyiWA 2ms3796kbC++174.8kb2023-05-03 21:46:092023-05-03 21:46:11

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-03 21:46:11]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3796kb
  • [2023-05-03 21:46:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int N = 107;
const double INF = 1e47;

struct Point {
	int x, y;
	Point() {}
	Point(int _x, int _y): x(_x), y(_y) {}
	Point operator-(const Point& p) const {
		return Point(x - p.x, y - p.y);
	}
	int operator*(const Point& p) const {
		return x * p.y - p.x * y;
	}
	bool operator<(const Point& p) const {
		return x != p.x ? x < p.x : y < p.y;
	}
	bool operator==(const Point& p) const {
		return x == p.x && y == p.y;
	}
	int dot(const Point& p) const {
		return x * p.x + y * p.y;
	}
	int d2() const {
		return x * x + y * y;
	}
	double len() const {
		return sqrt(d2());
	}
};

int sign(int x) {
	if (x == 0) {
		return 0;
	}
	return x > 0 ? 1 : -1;
}

bool intersect(const Point& a, const Point& b, const Point& c, const Point& d) {
	return sign((b - a) * (c - a)) * sign((b - a) * (d - a)) <= 0 &&
		sign((d - c) * (a - c)) * sign((d - c) * (b - c)) < 0;
}

bool belongs(const Point& a, const Point& b, const Point& c) {
	return (b - a) * (c - a) == 0 && (b - a).dot(c - a) >= 0 && (a - b).dot(c - b) >= 0;
}

int area(const vector<Point>& p) {
	int res = 0;
	FOR(i, 0, SZ(p) - 1) {
		res += (p[i + 1] - p[0]) * (p[i] - p[0]);
	}
	return abs(res);
}

bool segmentInside(const vector<Point>& p, const Point& a, const Point& b, bool needStrictly) {
	int i = find(ALL(p), a) - p.begin(), j = find(ALL(p), b) - p.begin();
	if (((i + 1) % SZ(p) == j || (j + 1) % SZ(p) == i) && needStrictly) {
		return false;
	}
	vector<Point> ij, ji;
	for (int k = i; ; k = (k + 1) % SZ(p)) {
		ij.push_back(p[k]);
		if (k == j) {
			break;
		}
	}
	for (int k = j; ; k = (k + 1) % SZ(p)) {
		ji.push_back(p[k]);
		if (k == i) {
			break;
		}
	}
	return area(ij) + area(ji) == area(p);
}

double dist[N][N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(10);
	vector<Point> p[2];
	FOR(i, 0, 2) {
		int n;
		cin >> n;
		p[i].resize(n);
		for (Point& pij : p[i]) {
			cin >> pij.x >> pij.y;
		}
	}
	int iMinPoint[2] = {0, 0};
	FOR(j, 0, 2) {
		FOR(i, 0, SZ(p[j])) {
			if (p[j][i] < p[j][iMinPoint[j]]) {
				iMinPoint[j] = i;
			}
		}
	}
	vector<int> U, D;
	vector<int> idxes(SZ(p[0]));
	iota(ALL(idxes), 0);
	sort(ALL(idxes), [&](int i, int j) {return p[0][i] < p[0][j];});
	for (int j : idxes) {
		while (SZ(U) > 1 && (p[0][U.back()] - p[0][SZ(U) - 2]) * (p[0][j] - p[0][SZ(U) - 2]) >= 0) {
			U.pop_back();
		}
		while (SZ(D) > 1 && (p[0][D.back()] - p[0][SZ(D) - 2]) * (p[0][j] - p[0][SZ(D) - 2]) <= 0) {
			D.pop_back();
		}
		U.push_back(j);
		D.push_back(j);
	}
	vector<int> convex = D;
	RFOR(j, SZ(U) - 1, 0) {
		convex.push_back(U[j]);
	}
	/*for (int idx : convex) {
		cerr << idx << " ";
	}
	cerr << endl;*/
	assert(convex[0] == iMinPoint[0] && convex.back() == iMinPoint[0]);
	double ans = 0;
	FOR(i, 0, SZ(convex) - 1) {
		const Point& a = p[0][convex[i]], b = p[0][convex[i + 1]];
		vector<Point> points;
		for (int j = convex[i]; ; j = (j + 1) % SZ(p[0])) {
			points.push_back(p[0][j]);
			if (j == convex[i + 1]) {
				break;
			}
		}
		int s = 0, t = SZ(points) - 1;
		bool inside = false;
		FOR(j, iMinPoint[1], iMinPoint[1] + SZ(p[1])) {
			const Point& c = p[1][j], d = p[1][(j + 1) % SZ(p[1])];
			if (belongs(a, b, c)) {
				inside = (b - a) * (d - a) > 0;
			}
			else {
				inside ^= intersect(a, b, c, d);
			}
			if (inside || belongs(a, b, d)) {
				points.push_back(d);
			}
		}
		int m = SZ(points);
		FOR(j, 0, m) {
			dist[j][j] = 0;
			FOR(k, j + 1, m) {
				dist[j][k] = dist[k][j] = INF;
				double len = (points[k] - points[j]).len();
				bool can = true;
				const Point& c = points[j], d = points[k];
				FOR(it, 0, 2) {
					FOR(l, 0, SZ(p[it])) {
						const Point& e = p[it][l], f = p[it][(l + 1) % SZ(p[it])];
						if ((d - c) * (f - e) == 0) {
							continue;
						}
						can &= !intersect(c, d, e, f);
					}
				}
				if (!can) {
					continue;
				}
				if ((j <= t) ^ (k <= t)) {
					dist[j][k] = dist[k][j] = len;
					continue;
				}
				if (j <= t) {
					can &= !segmentInside(p[0], c, d, true);
				}
				else {
					can &= segmentInside(p[1], c, d, false);
				}
				if (can) {
					dist[j][k] = dist[k][j] = len;
				}
			}
		}
		FOR(l, 0, m) {
			FOR(j, 0, m) {
				FOR(k, 0, m) {
					dist[j][k] = min(dist[j][k], dist[j][l] + dist[k][l]);
				}
			}
		}
		//cerr << dist[s][t] << endl;
		ans += dist[s][t];
	}
	cout << ans << "\n";
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3796kb

input:

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

output:

3.4142135624

result:

ok found '3.4142136', expected '3.4142136', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

5
1 1
5 1
5 5
3 3
1 5
4
0 0
6 0
6 6
0 6

output:

16.0000000000

result:

ok found '16.0000000', expected '16.0000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

5
1 1
5 1
5 5
3 3
1 5
5
0 0
6 0
6 6
3 4
0 6

output:

16.4721359550

result:

ok found '16.4721360', expected '16.4721360', error '0.0000000'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3752kb

input:

5
2 2
6 2
6 6
4 4
2 6
4
0 0
8 0
8 8
0 8

output:

16.0000000000

result:

ok found '16.0000000', expected '16.0000000', error '0.0000000'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3728kb

input:

5
2 2
6 2
6 6
4 4
2 6
5
0 0
8 0
8 8
4 5
0 8

output:

16.4721359550

result:

ok found '16.4721360', expected '16.4721360', error '0.0000000'

Test #6:

score: -100
Wrong Answer
time: 2ms
memory: 3588kb

input:

12
1 1
1 4
-1 4
-1 1
-4 1
-4 -1
-1 -1
-1 -4
1 -4
1 -1
4 -1
4 1
12
2 2
2 5
-2 5
-2 2
-5 2
-5 -2
-2 -2
-2 -5
2 -5
2 -2
5 -2
5 2

output:

28.9442719100

result:

wrong answer 1st numbers differ - expected: '25.8885438', found: '28.9442719', error = '0.1180340'