QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#781942 | #8054. Map 2 | ucup-team1004 | WA | 1ms | 3924kb | C++17 | 3.4kb | 2024-11-25 18:07:22 | 2024-11-25 18:07:23 |
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 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){
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
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3924kb
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: 3864kb
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 206.811852372481761 34.669871646719432 115.277925033373150 117.153745138599816 87.86353054...
result:
wrong answer 12th numbers differ - expected: '43.9317653', found: '206.8118524', error = '3.7075698'