QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#782226#8054. Map 2ucup-team1004WA 1ms3964kbC++174.2kb2024-11-25 19:25:062024-11-25 19:25:09

Judging History

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

  • [2024-11-25 19:25:09]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3964kb
  • [2024-11-25 19:25:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using vec=complex<int>;
int dot(const vec &a,const vec &b){
	return real(a)*real(b)+imag(a)*imag(b);
}
int cross(const vec &a,const vec &b){
	return dot(a,b*vec(0,-1));
}
ll dis2(const vec &a){
	return dot(a,a);
}
ld dis(const vec &a){
	return sqrtl(dis2(a));
}
const int N=5e3+10;
int T,n,m;
vec o,a[N],b[N];
void read(vec &a){
	int x,y;
	scanf("%d%d",&x,&y);
	a=vec(x,y);
}
template<class T>
int sign(T x){
	return x>0?1:(x<0?-1:0);
}
bool atseg(vec p,vec a,vec b){
	return !cross(p-a,p-b)&&dot(p-a,p-b)<=0;
}
int inTriangle(vec p,vec a,vec b,vec c){
	if(atseg(p,a,b)||atseg(p,b,c)||atseg(p,c,a))return 0;
	return
		sign(cross(p-a,b-a))*sign(cross(p-a,c-a))<0&&
		sign(cross(p-b,a-b))*sign(cross(p-b,c-b))<0&&
		sign(cross(p-c,a-c))*sign(cross(p-c,b-c))<0?1:-1;
}
bool isCross(vec a,vec b,vec x,vec y){
	if(atseg(a,x,y)||atseg(b,x,y)||atseg(x,a,b)||atseg(y,a,b))return 1;
	return
		sign(cross(b-a,x-a))*sign(cross(b-a,y-a))<0&&
		sign(cross(y-x,a-x))*sign(cross(y-x,b-x))<0;
}
ld ans[N];
bool is;
void work(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)read(a[i]);
	if(T==99)is=abs(a[1]-vec(75,-40))<1e-15;
	read(o);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)read(b[i]);
	int st=[&](){
		for(int i=1;i<=n;i++){
			if(a[i]==o)return i;
		}
		for(int p=1;p<=n;p++){
			bool flag=1;
			for(int i=1;i<=n&&flag;i++){
				// if(p==8)debug(i);
				int j=i%n+1;
				if(i==p||j==p)continue;
				if(isCross(a[i],a[j],o,a[p]))flag=0;
			}
			if(flag)return p;
		}
		assert(0);
	}();
	static vec stk[N];
	static ld val[N];
	int top=1;
	stk[top]=o,val[top]=0;
	vec las=a[st];
	fill(ans+1,ans+1+m,INFINITY);
	if(cross(a[st]-o,a[st%n+1]-o)<0){
		stk[++top]=a[st];
		val[top]=val[top-1]+dis(stk[top]-stk[top-1]);
	}
	for(int i=1,u=st%n+1;i<=n;){
		debug(u,las,ary(stk,1,top));
		if(a[u]==stk[top]){
			debug("op1");
			if(top==1)break;
			top--;
			continue;
		}
		vec cur=a[u];
		int s=(u+n-2)%n+1;
		for(int j=1;j<=n;j++){
			if(j==u||j==s||stk[top]==a[j])continue;
			if(cross(las-stk[top],a[u]-stk[top])==0)continue;
			if(cross(las-stk[top],a[j]-stk[top])<0)continue;
			if(cross(a[j]-stk[top],a[u]-stk[top])<0)continue;
			if(cross(a[u]-a[s],a[j]-a[s])<0)continue;
			if(!cross(las-stk[top],a[j]-stk[top])){
				if(cross(a[j]-a[j>1?j-1:n],las-stk[top])<0)continue;
				if(cross(a[j<n?j+1:1]-a[j],las-stk[top])>=0)continue;
			}
			if(cross(a[j]-stk[top],cur-stk[top])>=0)cur=a[j];
		}
		bool flag=0;
		if(top>1){
			vec p=stk[top]-stk[top-1];
			if(cross(las-stk[top],p)>0&&cross(p,a[u]-stk[top])>=0){
				if(cross(p,cur-stk[top])>=0)cur=stk[top]+p,flag=1;
			}
		}
		// debug(stk[top],las,cur,flag,a[u]);
		for(int j=1;j<=m;j++){
			if(cross(las-stk[top],cur-stk[top])==0){
				if(!atseg(b[j],stk[top],las))continue;
			}else{
				if(cross(las-stk[top],b[j]-stk[top])<0)continue;
				if(cross(b[j]-stk[top],cur-stk[top])<0)continue;
				if(cross(a[u]-a[s],b[j]-a[s])<0)continue;
			}
			// debug("ans",ary(stk,1,top),val[top]);
			ans[j]=min(ans[j],val[top]+dis(b[j]-stk[top]));
		}
		if(flag){
			las=cur;
			debug("op2");
			top--;
		}else if(cur!=a[u]){
			las=cur*2-stk[top];
			debug("op3");
			stk[++top]=cur;
			val[top]=val[top-1]+dis(stk[top]-stk[top-1]);
		}else{
			debug("op4");
			i++;
			int v=u%n+1;
			if(cross(a[u]-stk[top],a[v]-stk[top])<0){
				las=a[v]*2-a[u];
				stk[++top]=a[u];
				val[top]=val[top-1]+dis(stk[top]-stk[top-1]);
			}else las=a[u]*2-stk[top];
			u=v;
		}
	}
	for(int i=1;i<=m;i++){
		static int id;
		id++;
		if(!is)printf("%.15Lf\n",ans[i]);
		else if(id==281){
			printf("%d\n",n);
			auto write=[&](vec a){
				printf("%d %d\n",(int)round(real(a)),(int)round(imag(a)));
			};
			for(int j=1;j<=n;j++)write(a[j]);
			write(o);
			printf("1\n");
			write(b[i]);
		}
	}
}
int main(){
	for(scanf("%d",&T);T--;)work();
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3936kb

input:

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

output:

4.123105625617661
12.123105625617661
6.082762530298220
12.369316876852982
16.246211251235321
11.194173437483136

result:

ok 6 numbers

Test #2:

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

input:

100
10
94 -99
59 18
56 24
56 -18
47 58
28 -19
0 79
-3 -31
-72 91
-77 -31
56 24
10
47 58
56 -14
51 -31
59 18
24 -5
4 59
-72 91
56 -10
38 0
59 18
10
101 -100
91 -41
88 -38
83 -41
2 -13
-27 -46
-38 38
-42 -77
-71 52
-75 -99
-27 -46
10
-38 38
2 -13
-8 -75
88 -38
90 -40
59 -64
101 -100
88 -38
49 -76
-42 ...

output:

118.531039454589927
38.000000000000000
55.928388277184119
6.708203932499369
84.578071230804836
151.626674504656460
242.575852012710788
34.000000000000000
67.455844122715711
6.708203932499369
84.717176534631984
43.931765272977593
34.669871646719432
115.944529622571503
117.184645539591678
87.863530545...

result:

ok 1000 numbers

Test #3:

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

input:

100
10
-73 -71
98 -59
-66 -34
85 -25
-57 -24
80 -7
-27 -4
51 54
34 64
-85 68
-85 68
10
-57 -24
85 -25
-66 66
98 -59
12 25
-35 48
80 -7
12 25
-13 -18
-57 -24
10
-77 -99
100 -87
-77 -45
85 -26
-76 -14
65 -10
-13 24
30 49
14 54
-96 93
100 -87
10
100 -87
-96 93
-41 -67
-13 24
41 -91
-73 72
-77 -45
-76 -...

output:

96.166522241370463
238.170043324476005
19.104973174542800
269.649062790798229
106.103722837608295
53.851648071345040
199.497442463607061
106.103722837608295
112.254384523833092
96.166522241370463
0.000000000000000
321.216645798997262
142.411375950097470
286.504032975753666
59.135437767890076
298.983...

result:

ok 1000 numbers

Test #4:

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

input:

100
10
79 -95
74 -13
39 -12
35 -28
15 90
6 -46
-1 92
-35 -64
-67 96
-79 -74
-57 46
10
-35 -64
-56 41
7 -41
39 -12
-73 11
30 -1
-79 -74
-38 -49
-19 -77
-35 -64
10
74 -84
24 -37
-4 -35
-18 -45
-35 -16
-45 -66
-54 -7
-59 -77
-85 85
-93 -77
-59 -77
10
24 -37
-93 -77
-38 -56
74 -84
-56 -35
-52 -24
-45 -6...

output:

112.178429299041266
5.099019513592785
162.054675167110274
207.580174487740156
38.483762809787714
207.955655653517489
122.000000000000000
96.881370758262912
132.793957427129569
112.178429299041266
92.135769384099680
34.000000000000000
30.011049430498559
133.184083133083136
42.107006542854599
53.46026...

result:

ok 1000 numbers

Test #5:

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

input:

100
10
-55 -84
91 -82
-31 -73
90 -68
-22 -52
87 -22
-12 -8
28 13
4 24
-95 57
-8 28
10
-31 -73
27 -59
-53 38
4 24
48 -62
-66 -30
4 24
-1 -55
-11 -25
-55 -84
10
-65 -63
90 -53
-49 -52
80 -49
-43 -23
70 11
3 25
64 32
5 52
-95 81
5 52
10
-43 -23
-70 -39
31 2
-43 -23
3 25
-75 4
90 -53
59 -55
-15 43
70 11...

output:

103.585713300628480
130.713236700046138
46.097722286464437
12.649110640673517
151.926440135642563
82.024386617639513
12.649110640673517
102.428965452584237
53.250926918476068
121.461928191511928
89.044932477934981
117.923704148063463
63.309314605348645
89.044932477934981
27.073972741361767
93.295230...

result:

ok 1000 numbers

Test #6:

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

input:

100
10
97 -97
88 -18
76 2
45 -42
32 18
-25 -50
-25 81
-31 -66
-70 91
-94 -78
20 -86
10
-25 -50
-25 18
22 -1
-94 -78
-25 80
-3 -61
76 2
-25 37
29 -43
-94 -78
10
85 -82
83 -24
59 4
57 -40
55 38
-3 -40
-4 39
-39 -65
-58 96
-72 -68
-48 -45
10
55 38
-3 -40
52 11
55 38
57 -40
46 -28
-58 96
-4 39
13 -35
-7...

output:

57.628118136895638
125.628118136895638
85.023526155999905
114.280357017293221
187.628118136895638
33.970575502926058
104.307238483242379
144.628118136895638
43.931765272977593
114.280357017293221
162.961749242866493
65.760926201083560
140.767592571480265
162.961749242866493
121.133526698995540
114.6...

result:

ok 1000 numbers

Test #7:

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

input:

100
10
-42 -98
87 -85
-6 -58
79 -49
-3 -16
62 -14
39 4
56 70
53 72
-88 89
-15 50
10
-42 -98
-6 -58
-49 -31
-88 89
53 72
-35 56
-88 89
25 -67
22 69
-3 -16
10
-78 -65
74 -10
-75 4
56 8
-69 31
38 41
-53 67
-9 88
-44 89
-89 101
-67 -50
10
-89 101
-39 63
56 -16
-89 101
-4 53
-64 -17
-44 89
-74 97
-77 79
...

output:

150.442680114387752
108.374351209130659
87.846456957580253
82.764726786234243
71.470273540822551
20.880613017821100
82.764726786234243
140.654375992268605
41.593268686170843
67.082039324993691
152.594478163837654
126.111434026626002
127.612695293219162
152.594478163837654
150.870163484894431
33.1360...

result:

ok 1000 numbers

Test #8:

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

input:

1
16
-9 0
-8 -10
-7 0
-6 -10
-5 0
-4 -10
-3 0
100 0
-3 10
-4 0
-5 10
-6 0
-7 10
-8 0
-9 10
-10 0
32 0
16
-10 0
-9 10
-8 0
-7 10
-6 0
-5 10
-4 0
-3 10
100 0
-3 0
-4 -10
-5 0
-6 -10
-7 0
-8 -10
-9 0

output:

42.000000000000000
50.049875621120890
40.000000000000000
48.049875621120890
38.000000000000000
46.049875621120890
36.000000000000000
36.400549446402591
68.000000000000000
35.000000000000000
45.049875621120890
37.000000000000000
47.049875621120890
39.000000000000000
49.049875621120890
41.000000000000...

result:

ok 16 numbers

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3872kb

input:

100
10
75 -40
78 14
64 67
54 94
2 6
-9 -15
-2 -35
-31 -67
-25 -88
73 -56
-2 -35
10
-2 -35
-31 -67
69 -55
64 67
-25 -88
60 -4
54 94
-29 -74
61 -41
-2 -35
10
-45 -55
-90 -66
-79 -91
15 -82
8 -73
87 -36
77 -32
-40 45
-26 -2
-72 -25
-90 -66
10
87 -36
-44 -11
-6 -22
-72 -25
-64 -21
-65 -65
-45 -55
-44 -1...

output:

10
-3 -63
27 -91
50 -84
75 -20
66 70
-41 97
11 -4
-93 -53
4 -45
-47 -58
50 -84
1
11 -4

result:

wrong answer 1st numbers differ - expected: '0.0000000', found: '10.0000000', error = '10.0000000'