QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#781956#8054. Map 2ucup-team1004WA 1ms3992kbC++173.4kb2024-11-25 18:11:072024-11-25 18:11:09

Judging History

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

  • [2024-11-25 18:11:09]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3992kb
  • [2024-11-25 18:11:07]
  • 提交

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 atline(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(atline(p,a,b)||atline(p,b,c)||atline(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];
void work(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)read(a[i]);
	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];
	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==s||stk[top]==a[j])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],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]=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++){
		printf("%.15Lf\n",ans[i]);
	}
}
int main(){
	for(scanf("%d",&T);T--;)work();
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

wrong answer 691st numbers differ - expected: '256.5850249', found: '345.1287994', error = '0.3450855'