QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#102882 | #3184. Around the Track | PetroTarnavskyi# | WA | 2ms | 3796kb | C++17 | 4.8kb | 2023-05-03 19:28:19 | 2023-05-03 19:28:21 |
Judging History
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 = U;
RFOR(j, SZ(D) - 1, 0) {
convex.push_back(D[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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3724kb
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: 2ms
memory: 3796kb
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: 3568kb
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: 0ms
memory: 3756kb
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: 3616kb
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:
46.4721359550
result:
wrong answer 1st numbers differ - expected: '25.8885438', found: '46.4721360', error = '0.7950850'