QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#782107 | #8054. Map 2 | ucup-team1004 | WA | 1ms | 3980kb | C++17 | 3.9kb | 2024-11-25 18:55:36 | 2024-11-25 18:55:37 |
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);
}
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'