QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#782226 | #8054. Map 2 | ucup-team1004 | WA | 1ms | 3964kb | C++17 | 4.2kb | 2024-11-25 19:25:06 | 2024-11-25 19:25:09 |
Judging History
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'