QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#330098#8054. Map 2ucup-team266#WA 4ms3948kbC++235.5kb2024-02-17 12:21:372024-02-17 12:21:38

Judging History

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

  • [2024-02-17 12:21:38]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3948kb
  • [2024-02-17 12:21:37]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
#define double long double
#define x first
#define y second
void die(string S){puts(S.c_str());exit(0);}
using point=pair<double,double>;
const double eps=1e-15;
point p[5005],sp,qp[5005];
int n,q;
vector<array<int,3>> tri;
const double operator ^(const point &a,const point &b)
{
	return a.x*b.y-a.y*b.x;
}
const point operator -(const point &a,const point &b)
{
	return point(a.x-b.x,a.y-b.y);
}
bool sameSide(point M,point N,point A,point B)
{
	return ((M-N)^(A-N))*((M-N)^(B-N))>-eps;
}
bool inside(point A,point B,point C,point P)
{
	return sameSide(A,B,C,P)&&sameSide(A,C,B,P)&&sameSide(B,C,A,P);
}
double dist2(const point &a,const point &b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
double dist(const point &a,const point &b)
{
	return sqrt(dist2(a,b));
}
void decomp(vector<int> vec)
{
	if(sz(vec)==3)
	{
		tri.push_back({vec[0],vec[1],vec[2]});
		return ;
	}
	if(((p[vec[2]]-p[vec[1]])^(p[vec[0]]-p[vec[1]]))<-eps)
	{
		vec.pb(vec[0]);
		vec.erase(vec.begin());
		decomp(vec);
		return ;
	}
	pair<double,int> pr=mp(1e18,-1);
	for(int i=3;i<sz(vec);i++)
		if(inside(p[vec[0]],p[vec[1]],p[vec[2]],p[vec[i]]))
			pr=min(pr,mp(dist2(p[vec[1]],p[vec[i]]),i));
	if(pr.second==-1)
	{
		tri.push_back({vec[0],vec[1],vec[2]});
		vec.erase(vec.begin()+1);
		decomp(vec);
	}
	else
	{
		vector<int> v1,v2;
		for(int i=1;i<=pr.second;i++)
			v1.pb(vec[i]);
		for(int i=pr.second;i<sz(vec);i++)
			v2.pb(vec[i]);
		v2.pb(vec[0]);
		v2.pb(vec[1]);
		decomp(v1);
		decomp(v2);
	}
}
vector<int> G[5005];
int getIndex(const point &po)
{
	for(int i=1;i<=sz(tri);i++)
		if(inside(p[tri[i-1][0]],p[tri[i-1][1]],p[tri[i-1][2]],po))
			return i;
	assert(0);
	return -1;
}
vector<int> ret;
bool dfs(int u,int fa,int nd)
{
	ret.pb(u);
	if(u==nd)
		return true;
	for(auto v:G[u])
		if(v!=fa)
			if(dfs(v,u,nd))
				return true;
	ret.pop_back();
	return false;
}
vector<int> getRoute(int st,int nd)
{
	ret.clear();
	assert(dfs(st,0,nd));
	return ret;
}
pii getDiagonal(int A,int B)
{
	vector<int> ans;
	map<int,int> Mp;
	for(int i=0;i<3;i++)
		Mp[tri[A-1][i]]++;
	for(int i=0;i<3;i++)
		Mp[tri[B-1][i]]++;
	for(auto pr:Mp)
		if(pr.second==2)
			ans.pb(pr.first);
	assert(sz(ans)==2);
	return mp(ans[0],ans[1]);
}
double getAnswer(int st,int nd,point A,point B,vector<int> route)
{
	if(sz(route)==1) return dist(A,B);
	p[0]=A;
	p[n+1]=B;
	deque<int> dq;
	int apex=0;
	double ans=0;
	vector<pii> vd;
	for(int i=1;i<sz(route);i++)
		vd.pb(getDiagonal(route[i-1],route[i]));
	if(((p[vd[0].first]-A)^(p[vd[0].second]-A))<eps)
		swap(vd[0].first,vd[0].second);
	dq.push_back(0);
	dq.push_front(vd[0].first);
	dq.push_back(vd[0].second);
	auto extend=[&](int a,int b)
	{
		if(b==dq.front()||b==dq.back())
			swap(a,b);
		if(a==dq.front())
		{
			while(dq.back()!=apex&&((p[b]-p[dq.back()])^(p[dq.back()]-p[dq[sz(dq)-2]]))>eps)
				dq.pop_back();
			if(dq.back()!=apex)
				dq.push_back(b);
			else
			{
				while(sz(dq)>1&&((p[b]-p[dq.back()])^(p[dq[sz(dq)-2]]-p[dq.back()]))>eps)
				{
					ans+=dist(p[dq.back()],p[dq[sz(dq)-2]]);
					dq.pop_back();
					apex=dq.back();
				}
				dq.push_back(b);
			}
		}
		else
		{
			while(dq.front()!=apex&&((p[b]-p[dq[0]])^(p[dq[0]]-p[dq[1]]))<-eps)
				dq.pop_front();
			if(dq.front()!=apex)
				dq.push_front(b);
			else
			{
				while(sz(dq)>1&&((p[b]-p[dq[0]])^(p[dq[1]]-p[dq[0]]))<-eps)
				{
					ans+=dist(p[dq[0]],p[dq[1]]);
					dq.pop_front();
					apex=dq[0];
				}
				dq.push_front(b);
			}
		}
	};
	for(int i=1;i<sz(vd);i++)
		extend(vd[i].first,vd[i].second);
	extend(vd.back().first,n+1);
	if(dq.back()==n+1)
	{
		while(dq.back()!=apex)
		{
			ans+=dist(p[dq.back()],p[dq[sz(dq)-2]]);
			dq.pop_back();
		}
		return ans;
	}
	else
	{
		while(dq.front()!=apex)
		{
			ans+=dist(p[dq[0]],p[dq[1]]);
			dq.pop_front();
		}
		return ans;
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
			G[i].clear();
		for(int i=1;i<=n;i++)
			cin>>p[i].x>>p[i].y;
		cin>>sp.x>>sp.y;
		cin>>q;
		for(int i=1;i<=q;i++)
			cin>>qp[i].x>>qp[i].y;
		vector<int> vec;
		for(int i=1;i<=n;i++)
			vec.pb(i);
		tri.clear();
		decomp(vec);
		map<pii,int> Mp;
		auto Try=[&](int a,int b,const int &c)
		{
			if(a>b) swap(a,b);
			if(Mp.count(mp(a,b)))
			{
				int x=Mp[mp(a,b)];
				G[x].pb(c);
				G[c].pb(x);
			}
			else
				Mp[mp(a,b)]=c;
		};
		for(int i=1;i<=sz(tri);i++)
		{
			Try(tri[i-1][0],tri[i-1][1],i);
			Try(tri[i-1][2],tri[i-1][1],i);
			Try(tri[i-1][0],tri[i-1][2],i);
		}
		int st=getIndex(sp);
		for(int i=1;i<=q;i++)
		{
			int nd;
			vector<int> route=getRoute(st,nd=getIndex(qp[i]));
			double ans=getAnswer(st,nd,sp,qp[i],route);
			cout<<fixed<<setprecision(12)<<ans<<endl;
		}
	}
	return 0;
}

详细

Test #1:

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

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.123105625618
12.123105625618
6.082762530298
12.369316876853
16.246211251235
11.194173437483

result:

ok 6 numbers

Test #2:

score: -100
Wrong Answer
time: 4ms
memory: 3836kb

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:

193.210839833086
38.000000000000
55.928388277184
6.708203932499
43.185645763378
62.681735776859
144.474911316810
34.000000000000
135.372230151076
6.708203932499
84.717176534632
43.931765272978
34.669871646719
115.944529622572
117.184645539592
87.863530545955
138.924439894498
115.944529622572
81.7067...

result:

wrong answer 1st numbers differ - expected: '118.5310395', found: '193.2108398', error = '0.6300443'