QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#330098 | #8054. Map 2 | ucup-team266# | WA | 4ms | 3948kb | C++23 | 5.5kb | 2024-02-17 12:21:37 | 2024-02-17 12:21:38 |
Judging History
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'