QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#782107#8054. Map 2ucup-team1004WA 1ms3980kbC++173.9kb2024-11-25 18:55:362024-11-25 18:55:37

Judging History

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

  • [2024-11-25 18:55:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3980kb
  • [2024-11-25 18:55:36]
  • 提交

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);
}
ld calc(vec p,vec a,vec b){
	if(dot(p-a,b-a)<0)return dis(a-p);
	if(dot(p-b,a-b)<0)return INFINITY;
	return abs(cross(p-a,p-b))/dis(a-b);
}
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;
}
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(97,-97))<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;
		}
		int p=1;
		ld val=calc(o,a[1],a[2]);
		for(int i=2;i<=n;i++){
			ld dis=calc(o,a[i],a[i%n+1]);
			if(dis<val)val=dis,p=i;
		}
		return p;
	}();
	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);
	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==271){
			printf("%d\n",n);
			for(int j=1;j<=n;j++){
				printf("%d %d\n",int(real(a[j])+1e-15),int(imag(a[j])+1e-15));
			}
			printf("1\n");
			printf("%d %d\n",int(real(b[i])+1e-15),int(imag(b[i])+1e-15));
		}
	}
}
int main(){
	for(scanf("%d",&T);T--;)work();
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif

详细

Test #1:

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

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: 1ms
memory: 3980kb

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: 3944kb

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: 1ms
memory: 3900kb

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: -100
Wrong Answer
time: 1ms
memory: 3928kb

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:

10
57 -84
48 4
43 31
29 -31
28 52
-9 -52
-9 59
-29 -76
-75 87
-77 -82
1
48 4

result:

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