QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87292#3184. Around the TrackIgnotusWA 223ms4396kbC++146.2kb2023-03-12 12:05:412023-03-12 12:05:45

Judging History

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

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

answer

#include <bits/stdc++.h>

const int N = 55;
const double eps = 1e-9;
const double PI = acos(-1.0);

// std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
std::mt19937 rng(41);
std::uniform_real_distribution <> rel(0, 0.5);

const double rotate_deg = rel(rng) * PI;

struct point{
	double x, y;
}E;

struct polygon{
	int n;
	std::vector <point> a;
	point& operator [] (int i){return a[i];}
};

struct line{
	double k, b;
};

struct segment{
	point A, B;
	double k, b;
	segment(point _A, point _B){
		A = _A, B = _B;
		k = (A.y - B.y) / (A.x - B.x);
		b = A.y - k * A.x;
	}
};
segment Lray(E, E), Rray(E, E);


void print(point P){
    printf("(%.6lf, %.6lf)\n", P.x, P.y);
}

point rotate(point A, double deg){
	return {A.x * cos(deg) - A.y * sin(deg), A.x * sin(deg) + A.y * cos(deg)};
}

bool on_segment(point P, segment L){
	if(fabs(L.k * P.x + L.b - P.y) > eps) return 0;
	if(L.A.x > L.B.x) std::swap(L.A, L.B);
	return L.A.x - eps <= P.x && P.x <= L.B.x + eps;
}

bool point_in_polygon(point P, polygon G, bool flg){
	// P 向正右侧引出射线
	int cnt = 0;
	for(int i = 0; i < G.n; ++i){
		int u = i, v = (i + 1) % G.n;
		if(G[u].y < G[v].y) std::swap(u, v);
		segment L(G[u], G[v]);
		if(on_segment(P, L)) return flg; // 在边界上
		if(!(G[u].y >= P.y - eps && G[v].y + eps < P.y)) continue;
		double cross_x = (P.y - L.b) / L.k;
		if(cross_x >= P.x - eps) ++cnt;
	}
	return cnt & 1;
}

bool intersect(segment L, segment M, point &I){ // 是否与非端点相交 
	if(L.k == M.k) return 0; // 在题目中平行和重合都被视为合法 
	// L.k * x + L.b = y
    // M.k * x + M.b = y
    point P;
    P.x = (M.b - L.b) / (L.k - M.k), P.y = L.k * P.x + L.b;
    if(on_segment(P, L) && on_segment(P, M)){
        I = P;
        return 1;
    }
    else return 0;
}

polygon A, B;

void test1(){
	polygon G;
	G.n = 3;
	G.a.push_back({0, 0}), G.a.push_back({4, 2}), G.a.push_back({1, 4});
	point A = {-1, 2}, B = {-1, 4}, C = {-1, 0}, D = {0.5, 2}, E = {2, 1}, F = {2.0000001, 1};
	std::cerr << point_in_polygon(A, G, 1) << '\n';
	std::cerr << point_in_polygon(B, G, 1) << '\n';
	std::cerr << point_in_polygon(C, G, 1) << '\n';
	std::cerr << point_in_polygon(D, G, 1) << '\n';
	std::cerr << point_in_polygon(E, G, 1) << '\n';
	std::cerr << point_in_polygon(F, G, 1) << '\n';
}

bool valid[N << 1][N << 1];
double chk_x, chk_y, dis[N << 1][N << 1];
double f[N << 1][N << 1][2][2];

bool cro[2][N << 1][N << 1];

bool get_validity(int i, int j){
    point P, Q;
    if(i < A.n) P = A[i];
    else P = B[i - A.n];
    if(j < A.n) Q = A[j];
    else Q = B[j - A.n];
    // std::cerr << "i: " << i << " ", print(P);
    // std::cerr << "j: " << j << " ", print(Q);
    dis[i][j] = dis[j][i] = sqrtl((P.x - Q.x) * (P.x - Q.x) + (P.y - Q.y) * (P.y - Q.y));
    segment L(P, Q);
    std::vector <point> nds; // intersections
    for(int i = 0; i < A.n; ++i){
        int u = i, v = (i + 1) % A.n;
        segment M(A[u], A[v]);
        point R;
        if(intersect(L, M, R)) nds.push_back(R);
    }
    for(int i = 0; i < B.n; ++i){
        int u = i, v = (i + 1) % B.n;
        segment M(B[u], B[v]);
        point R;
        if(intersect(L, M, R)) nds.push_back(R);
    }
    nds.push_back(P), nds.push_back(Q);
    std::sort(nds.begin(), nds.end(), [&](point I, point J){return I.x == J.x ? I.y < J.y : I.x < J.x;});
    int siz = nds.size();
    // std::cerr << "size: " << siz << '\n';
    for(int i = 1; i < siz; ++i){
        point Midpoint = {(nds[i - 1].x + nds[i].x) / 2.0, (nds[i - 1].y + nds[i].y) / 2.0};
        if(point_in_polygon(Midpoint, A, 0) || !point_in_polygon(Midpoint, B, 1)) return 0;
    }
    point R;
    if(intersect(L, Lray, R)) cro[0][i][j] = cro[0][j][i] = 1;
    if(intersect(L, Rray, R)) cro[1][i][j] = cro[1][j][i] = 1;
    return 1;
}

int main(){
    // freopen("test.in", "r", stdin);
	// test1();
    E = {0, 0};
    std::cin >> A.n;
    for(int i = 0; i < A.n; ++i){
        double x, y;
        std::cin >> x >> y;
        point P = {x, y};
        P = rotate(P, rotate_deg);
        // print(P);
        A.a.push_back(P);
    }
    std::cin >> B.n;
    for(int i = 0; i < B.n; ++i){
        double x, y;
        std::cin >> x >> y;
        point P = {x, y};
        P = rotate(P, rotate_deg);
        // print(P);
        B.a.push_back(P);
    }
    chk_x = (A[0].x + A[1].x) / 2.0, chk_y = (A[0].y + A[1].y) / 2.0;
    // print({chk_x, chk_y});
    point tmp = {chk_x - 1e-3, chk_y};
    if(point_in_polygon(tmp, A, 0)) chk_x -= 1e-3;
    else chk_x += 1e-3;
    // print({chk_x, chk_y});
    Lray = segment({chk_x, chk_y}, {1e9, chk_y}), Rray = segment({chk_x, chk_y}, {-1e9, chk_y});
    // std::cerr << Lray.k << " " << Lray.b << " " << Rray.k << " " << Rray.b << '\n';
    for(int i = 0; i < A.n + B.n; ++i){
        valid[i][i] = 1;
        for(int j = i + 1; j < A.n + B.n; ++j){
            valid[i][j] = valid[j][i] = get_validity(i, j);
            // std::cerr << i << " " << j << " " << dis[i][j] << " " << valid[i][j] << " " << cro[0][i][j] << " " << cro[1][i][j] << '\n';
        }
    }
    double ans = 1e15;
    for(int st = 0; st < A.n + B.n; ++st){
        for(int i = 0; i <= A.n + B.n; ++i){
            for(int j = 0; j < A.n + B.n; ++j){
                for(int o = 0; o < 2; ++o){
                    for(int p = 0; p < 2; ++p) f[i][j][o][p] = 1e15;
                }
            }
        }
        f[0][st][0][0] = 0;
        for(int i = 1; i <= A.n + B.n; ++i){
            for(int j = 0; j < A.n + B.n; ++j){
                for(int o = 0; o < 2; ++o){
                    for(int p = 0; p < 2; ++p){
                        if(f[i - 1][j][o][p] >= 1e15) continue;
                        for(int k = 0; k < A.n + B.n; ++k) if(j != k && valid[j][k]){
                            double &t = f[i][k][o ^ cro[0][j][k]][p ^ cro[1][j][k]];
                            t = std::min(t, f[i - 1][j][o][p] + dis[j][k]);
                        }
                    }
                }
            }
        }
        for(int i = 3; i <= A.n + B.n; ++i) ans = std::min(ans, f[i][st][1][1]);
    }
    printf("%.9lf\n", ans);
	return 0;
}
// QOJ3184

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

3.414213562

result:

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

Test #2:

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

input:

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

output:

16.000000000

result:

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

Test #3:

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

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.472135955

result:

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

Test #4:

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

input:

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

output:

16.000000000

result:

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

Test #5:

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

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.472135955

result:

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

Test #6:

score: 0
Accepted
time: 3ms
memory: 3892kb

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:

25.888543820

result:

ok found '25.8885438', expected '25.8885438', error '0.0000000'

Test #7:

score: 0
Accepted
time: 3ms
memory: 3852kb

input:

8
1 1
15 1
15 7
14 7
14 2
2 2
2 7
1 7
15
0 0
16 0
16 8
13 8
12 4
11 6
10 3
9 6
8 5
7 6
6 3
5 6
4 4
3 8
0 8

output:

43.683238506

result:

ok found '43.6832385', expected '43.6832385', error '0.0000000'

Test #8:

score: 0
Accepted
time: 3ms
memory: 3848kb

input:

8
1 1
15 1
15 7
14 7
14 2
2 2
2 7
1 7
15
0 0
16 0
16 8
13 8
12 4
11 8
10 3
9 8
8 5
7 8
6 3
5 8
4 4
3 8
0 8

output:

43.683238506

result:

ok found '43.6832385', expected '43.6832385', error '0.0000000'

Test #9:

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

input:

8
1 1
15 1
15 7
14 7
14 2
2 2
2 7
1 7
15
0 0
16 0
16 8
13 8
12 4
11 7
10 3
9 7
8 5
7 7
6 3
5 7
4 4
3 8
0 8

output:

43.683238506

result:

ok found '43.6832385', expected '43.6832385', error '0.0000000'

Test #10:

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

input:

12
1 1
10 1
10 6
9 6
9 2
6 2
6 4
5 4
5 2
2 2
2 6
1 6
12
0 0
11 0
11 7
8 7
8 3
7 3
7 5
4 5
4 3
3 3
3 7
0 7

output:

33.152982445

result:

ok found '33.1529824', expected '33.1529824', error '0.0000000'

Test #11:

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

input:

7
1 1
5 1
5 19
4 2
3 18
2 2
1 19
9
0 0
6 0
6 20
5 20
4 3
3 19
2 3
1 20
0 20

output:

102.129031841

result:

ok found '102.1290318', expected '102.1290318', error '0.0000000'

Test #12:

score: 0
Accepted
time: 4ms
memory: 3996kb

input:

12
1 1
12 1
12 5
11 5
11 2
8 2
8 6
7 6
7 2
2 2
2 5
1 5
16
0 0
13 0
13 9
4 9
4 4
5 4
5 8
10 8
10 3
9 3
9 7
6 7
6 3
3 3
3 6
0 6

output:

36.796691275

result:

ok found '36.7966913', expected '36.7966913', error '0.0000000'

Test #13:

score: 0
Accepted
time: 3ms
memory: 3892kb

input:

12
1 1
12 1
12 5
11 5
11 2
8 2
8 6
7 6
7 2
2 2
2 5
1 5
12
0 0
13 0
13 9
4 9
4 4
5 4
5 8
6 8
6 3
3 3
3 6
0 6

output:

33.521451263

result:

ok found '33.5214513', expected '33.5214513', error '0.0000000'

Test #14:

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

input:

8
1 3
4 2
4 1
5 4
6 4
3 5
3 6
2 3
4
0 0
7 0
7 7
0 7

output:

14.422205102

result:

ok found '14.4222051', expected '14.4222051', error '0.0000000'

Test #15:

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

input:

8
1 2
2 1
4 3
4 5
5 5
4 6
2 4
2 2
4
2 0
6 4
4 7
0 3

output:

12.957417329

result:

ok found '12.9574173', expected '12.9574173', error '0.0000000'

Test #16:

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

input:

8
2 2
4 2
6 4
5 5
5 4
3 4
1 2
2 1
4
3 0
7 4
4 6
0 2

output:

12.957417329

result:

ok found '12.9574173', expected '12.9574173', error '0.0000000'

Test #17:

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

input:

12
1 3
4 2
9 2
9 1
10 4
10 9
11 9
8 10
3 10
3 11
2 8
2 3
4
0 3
9 0
12 9
3 12

output:

33.045188695

result:

ok found '33.0451887', expected '33.0451887', error '0.0000000'

Test #18:

score: 0
Accepted
time: 114ms
memory: 4316kb

input:

44
21 -7
21 5
20 5
20 -6
17 -6
17 4
16 4
16 -5
13 -5
13 3
12 3
12 -4
9 -4
9 2
8 2
8 -3
5 -3
5 1
4 1
4 -2
1 -2
1 0
-1 0
-1 -2
-4 -2
-4 1
-5 1
-5 -3
-8 -3
-8 2
-9 2
-9 -4
-12 -4
-12 3
-13 3
-13 -5
-16 -5
-16 4
-17 4
-17 -6
-20 -6
-20 5
-21 5
-21 -7
44
22 -8
22 6
19 6
19 -5
18 -5
18 5
15 5
15 -4
14 -4
...

output:

200.712066378

result:

ok found '200.7120664', expected '200.7120664', error '0.0000000'

Test #19:

score: 0
Accepted
time: 140ms
memory: 4112kb

input:

47
23 -13
22 11
21 -12
20 10
19 -11
18 9
17 -10
16 8
15 -9
14 7
13 -8
12 6
11 -7
10 5
9 -6
8 4
7 -5
6 3
5 -4
4 2
3 -3
2 1
1 -2
0 0
-1 -2
-2 1
-3 -3
-4 2
-5 -4
-6 3
-7 -5
-8 4
-9 -6
-10 5
-11 -7
-12 6
-13 -8
-14 7
-15 -9
-16 8
-17 -10
-18 9
-19 -11
-20 10
-21 -12
-22 11
-23 -13
47
24 -14
22 12
21 -11...

output:

603.514677955

result:

ok found '603.5146780', expected '603.5146780', error '0.0000000'

Test #20:

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

input:

8
-10 0
-10 -10
0 -10
10 -10
10 0
10 10
0 10
-10 10
8
-20 0
-20 -20
0 -20
20 -20
20 0
20 20
0 20
-20 20

output:

80.000000000

result:

ok found '80.0000000', expected '80.0000000', error '0.0000000'

Test #21:

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

input:

8
0 10
-10 10
-10 0
-10 -10
0 -10
10 -10
10 0
10 10
8
-20 0
-20 -20
0 -20
20 -20
20 0
20 20
0 20
-20 20

output:

80.000000000

result:

ok found '80.0000000', expected '80.0000000', error '0.0000000'

Test #22:

score: 0
Accepted
time: 3ms
memory: 3748kb

input:

8
10 0
10 10
0 10
-10 10
-10 0
-10 -10
0 -10
10 -10
8
-20 0
-20 -20
0 -20
20 -20
20 0
20 20
0 20
-20 20

output:

80.000000000

result:

ok found '80.0000000', expected '80.0000000', error '0.0000000'

Test #23:

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

input:

8
0 -10
10 -10
10 0
10 10
0 10
-10 10
-10 0
-10 -10
8
-20 0
-20 -20
0 -20
20 -20
20 0
20 20
0 20
-20 20

output:

80.000000000

result:

ok found '80.0000000', expected '80.0000000', error '0.0000000'

Test #24:

score: 0
Accepted
time: 23ms
memory: 3920kb

input:

4
-1000 -1000
0 0
1000 -1000
0 2000
50
1500 -1500
0 2500
-1500 -1500
-460 -730
-440 -720
-420 -710
-400 -700
-380 -690
-360 -680
-340 -670
-320 -660
-300 -650
-280 -640
-260 -630
-240 -620
-220 -610
-200 -600
-180 -590
-160 -580
-140 -570
-120 -560
-100 -550
-80 -540
-60 -530
-40 -520
-20 -510
0 -50...

output:

8560.623297837

result:

ok found '8560.6232978', expected '8560.6232978', error '0.0000000'

Test #25:

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

input:

4
-1 -1
1 -1
1 1
-1 1
16
1 3
-1 3
-1 2
-2 1
-3 1
-3 -1
-2 -1
-1 -2
-1 -3
1 -3
1 -2
2 -1
3 -1
3 1
2 1
1 2

output:

8.000000000

result:

ok found '8.0000000', expected '8.0000000', error '0.0000000'

Test #26:

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

input:

8
0 -1
3 -3
1 0
3 3
0 1
-3 3
-1 0
-3 -3
20
0 -2
7 -9
5 -6
6 -5
9 -7
2 0
9 7
6 5
5 6
7 9
0 2
-7 9
-5 6
-6 5
-9 7
-2 0
-9 -7
-6 -5
-5 -6
-7 -9

output:

25.298221281

result:

ok found '25.2982213', expected '25.2982213', error '0.0000000'

Test #27:

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

input:

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

output:

16.472135955

result:

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

Test #28:

score: 0
Accepted
time: 3ms
memory: 3912kb

input:

12
45 45
135 45
135 108
243 108
162 45
315 45
270 225
189 225
234 117
135 117
162 225
45 108
16
0 0
138 0
138 93
143 98
148 72
211 99
155 44
342 -45
360 270
180 270
192 125
175 122
169 125
161 270
0 180
0 90

output:

1158.353151750

result:

ok found '1158.3531518', expected '1158.3531517', error '0.0000000'

Test #29:

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

input:

4
-360 180
-297 270
-360 315
-405 225
6
-45 45
-270 270
-90 288
-90 450
-450 495
-540 135

output:

351.542597239

result:

ok found '351.5425972', expected '351.5425972', error '0.0000000'

Test #30:

score: 0
Accepted
time: 186ms
memory: 4244kb

input:

49
0 -1
460 -1
460 0
450 999
440 0
430 999
420 0
410 999
400 0
390 999
380 0
370 999
360 0
350 999
340 0
330 999
320 0
310 999
300 0
290 999
280 0
270 999
260 0
250 999
240 0
230 999
220 0
210 999
200 0
190 999
180 0
170 999
160 0
150 999
140 0
130 999
120 0
110 999
100 0
90 999
80 0
70 999
60 0
50 ...

output:

46374.304451082

result:

ok found '46374.3044511', expected '46374.3044511', error '0.0000000'

Test #31:

score: 0
Accepted
time: 214ms
memory: 4248kb

input:

50
-2255 1931
-2830 -3187
3406 -4113
-1883 -1838
2327 -1793
425 -1197
2782 -1197
-569 -601
-6 -1566
-1556 -1182
-793 124
3186 -187
481 523
1688 652
-1844 580
2726 1263
-1544 1419
2655 1961
-389 1916
2623 2899
-3785 4421
-4440 3211
-2902 3483
-4580 -3486
-2403 3382
-537 3211
425 2728
-1005 2345
-1696...

output:

67111.733745184

result:

ok found '67111.7337452', expected '67111.7337452', error '0.0000000'

Test #32:

score: 0
Accepted
time: 181ms
memory: 4328kb

input:

50
-4856 -2492
2539 -4838
4880 4847
-4864 -2066
2295 -4254
4404 4050
-4153 -1952
2123 -3843
3981 3355
-3486 -1880
1931 -3331
3514 2614
-2659 -1781
1764 -2833
3058 1817
-1907 -1667
1540 -2336
2515 1035
-1144 -1509
1404 -1895
2059 295
-389 -1338
1220 -1509
1540 -442
373 -1155
1084 -1167
661 -1083
1468...

output:

258611.429181497

result:

ok found '258611.4291815', expected '258611.4291815', error '0.0000000'

Test #33:

score: 0
Accepted
time: 216ms
memory: 4096kb

input:

50
1744 1847
-3538 3666
-3761 -4197
3609 -3486
4065 1874
1148 -2860
-1480 -3403
-2523 2444
-2299 -2917
-3050 -358
-2235 -3600
1456 -3046
3366 -160
3206 -3217
-3382 -3972
-2627 -3187
-3677 -3274
-3178 253
-2703 -571
-3370 3028
-2119 2800
-1068 -2548
2143 -912
-433 -643
-741 1521
-1037 -2420
-805 1646...

output:

55761.845617259

result:

ok found '55761.8456173', expected '55761.8456173', error '0.0000000'

Test #34:

score: 0
Accepted
time: 208ms
memory: 4396kb

input:

50
-4197 3951
885 2572
-3773 3127
-3294 -3459
-2710 2474
-2862 -3900
-3933 -3642
-4293 -4340
4392 -4355
-2255 -3786
-2235 2330
3374 1305
-1428 -3331
3026 340
3194 -3558
-1684 -3471
2822 1107
-1939 1889
-2011 -3558
4848 -4325
4373 4334
1104 1874
-2299 2486
-2363 -4128
-2607 2557
-2798 2587
-3286 -247...

output:

114150.091730721

result:

ok found '114150.0917307', expected '114150.0917307', error '0.0000000'

Test #35:

score: -100
Wrong Answer
time: 223ms
memory: 4216kb

input:

50
-4704 -4583
2 4349
4616 -4667
2962 4706
-3697 4562
-4920 -4766
-805 -3984
-1080 -1224
417 -942
2091 -3729
-70 -2150
405 -3630
1456 -4340
2726 -4140
2411 -2860
1160 -885
142 -46
174 708
54 1206
-729 253
-421 -373
-1716 -472
-1005 978
-190 2018
301 1634
765 735
521 397
1033 10
1096 735
757 1832
46 ...

output:

37120.701781389

result:

wrong answer 1st numbers differ - expected: '43688.2184848', found: '37120.7017814', error = '0.1503270'