QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#503346 | #6831. Known as the Fruit Brother | wangyue2017 | WA | 158ms | 14172kb | C++17 | 4.1kb | 2024-08-03 17:48:49 | 2024-08-03 17:48:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define D double
#define P pair<D,D>
#define x first
#define y second
P operator-(const P&a,const P&b){
return {a.x-b.x,a.y-b.y};
}
P operator+(const P&a,const P&b){
return {a.x+b.x,a.y+b.y};
}
P operator*(const P&a,const D&b){
return {a.x*b,a.y*b};
}
D length(const P&a){
return sqrt(a.x*a.x+a.y*a.y);
}
D dist(const P&a,const P&b){
return length(a-b);
}
D cross(const P&a,const P&b){
return a.x*b.y-a.y*b.x;
}
D dot(P a,P b){
return a.x*b.x+a.y*b.y;
}
const int N =200000;
P d[N];
P barr[50][4];
int n,m,cnt;
D R;
void add_line(P p,P a,P b){
P v=b-a;
P pro=a+v*(dot(v,p-a)/dot(v,v));
if(dist(pro,p)>R)return;
D res=sqrt(R*R-dist(p,pro)*dist(p,pro));
d[++cnt]=pro+(b-a)*(1.0/dist(b,a))*res;
d[++cnt]=pro-(b-a)*(1.0/dist(b,a))*res;
}
void add_point(P d){
for(int i=1;i<=n;++i){
for(int j=0;j<=3;++j){
add_line(d,barr[i][j],barr[i][(j+1)%4]);
}
}
}
D dis[1000][1000];
int sign(D a){
if(fabs(a<=1e-12))return 0;
if(a<0)return -1;
return 1;
}
void clac(int i,int j){
P a,b;
a=d[i],b=d[j];
if(i<=m){
if(dist(d[i],d[j])<=R+1e-12){
dis[i][j]=0;
return;
}
else{
a=a+(b-a)*(1/length(b-a))*R;
for(int i=1;i<=n;++i){
if(barr[i][0].first<=a.x&&a.x<=barr[i][2].first&&barr[i][0].y<=a.y&&a.y<=barr[i][2].y){
dis[i][j]=1e30;
return;
}
}
}
}
dis[i][j]=dist(b,a);
for(int ii=1;ii<=n;++ii){
for(int jj=0;jj<=3;++jj){
if(cross(b-a,barr[ii][jj]-a)*(cross(b-a,barr[ii][(jj+2)%4]-a))<0
&&cross(a-barr[ii][jj],barr[ii][(jj+2)%4]-barr[ii][jj])*cross(b-barr[ii][jj],barr[ii][(jj+2)%4]-barr[ii][jj])<0){
dis[i][j]=1e30;
return;
}
if(cross(b-a,barr[ii][jj]-a)*(cross(b-a,barr[ii][(jj+2)%4]-a))<0
&&cross(a-barr[ii][jj],barr[ii][(jj+2)%4]-barr[ii][jj])*cross(b-barr[ii][jj],barr[ii][(jj+2)%4]-barr[ii][jj])<0){
dis[i][j]=1e30;
return;
}
if(cross(b-a,barr[ii][jj]-a)*(cross(b-a,barr[ii][(jj+1)%4]-a))<0
&&cross(a-barr[ii][jj],barr[ii][(jj+1)%4]-barr[ii][jj])*cross(b-barr[ii][jj],barr[ii][(jj+1)%4]-barr[ii][jj])<0){
dis[i][j]=1e30;
return;
}
if(cross(b-a,barr[ii][jj]-a)*(cross(b-a,barr[ii][(jj+1)%4]-a))<0
&&cross(a-barr[ii][jj],barr[ii][(jj+1)%4]-barr[ii][jj])*cross(b-barr[ii][jj],barr[ii][(jj+1)%4]-barr[ii][jj])<0){
dis[i][j]=1e30;
return;
}
}
}
}
D ans[N];
bool in[N];
int pre[N];
int main(){
cin>>n>>m>>R;
for(int i=1;i<=n;++i){
D x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
barr[i][0]={x1,y1};barr[i][1]={x1,y2};barr[i][2]={x2,y2};barr[i][3]={x2,y1};
}
for(int i=1;i<=m;++i){
D x,y;
cin>>x>>y;
d[++cnt]={x,y};
}
for(int i=1;i<=n;++i){
for(int j=0;j<=3;++j){
d[++cnt]=barr[i][j];
}
}
D xs,ys,xt,yt;
cin>>xs>>ys>>xt>>yt;
d[++cnt]={xs,ys},d[++cnt]={xt,yt};
int S=cnt-1,T=cnt;
for(int i=1;i<=m;++i){
add_point(d[i]);
}
for(int i=1;i<=cnt;++i){
for(int j=1;j<=cnt;++j){
if(i==j)continue;
clac(i,j);
}
}
for(int i=1;i<=cnt;++i)ans[i]=1e30;
priority_queue<pair<double,int>, vector<pair<double,int> >, greater<pair<double,int> > >q;
ans[S]=0;
q.push({0,S});
while(!q.empty()){
auto [d,u]= q.top(); q.pop();
if (in[u]) continue;
in[u] = 1;
for (int i = 1; i <= cnt; i++) {
if (ans[u] + dis[u][i] < ans[i]) {
ans[i] = ans[u] + dis[u][i];
pre[i]=u;
q.push({ans[i], i});
}
}
}
printf("%.9lf",ans[T]);
// cout<<ans[T];
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7944kb
input:
1 2 2 0 2 7 4 -3 3 8 2 1 1 6 6
output:
9.543203767
result:
ok found '9.5432038', expected '9.5432038', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 7880kb
input:
1 2 3 0 2 7 4 -1 4 8 2 1 1 6 6
output:
7.930391429
result:
ok found '7.9303914', expected '7.9303914', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 10064kb
input:
1 2 2 2 2 7 4 -1 4 8 2 1 1 6 6
output:
7.634413615
result:
ok found '7.6344136', expected '7.6344136', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 10028kb
input:
1 2 1 0 2 7 4 -4 4 8 2 1 1 6 6
output:
9.738768883
result:
ok found '9.7387689', expected '9.7387689', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 7880kb
input:
1 2 2 0 2 7 5 -4 4 8 2 1 1 6 6
output:
9.647559034
result:
ok found '9.6475590', expected '9.6475590', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 7952kb
input:
1 0 114514 0 0 6 2 2 -1 5 3
output:
7.537319188
result:
ok found '7.5373192', expected '7.5373192', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 9992kb
input:
5 4 10 1 -99999 9 99999 11 -99999 19 99999 21 -99999 23 99999 -99999 999999 99999 1000000 -99999 -1000000 99999 -999999 0 0 10 0 20 0 24 7 -1 0 30 7
output:
1.000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 12028kb
input:
5 3 10 1 -99999 9 99999 11 -99999 19 99999 21 -99999 23 99999 -99999 999999 99999 1000000 -99999 -1000000 99999 -999999 0 0 10 0 20 0 -1 0 30 7
output:
3.206555616
result:
ok found '3.2065556', expected '3.2065556', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 8088kb
input:
5 4 1 1 -99999 9 99999 11 -99999 19 99999 21 -99999 23 99999 -99999 999999 99999 1000000 -99999 -1000000 99999 -999999 0 0 10 0 20 0 24 7 -1 0 30 7
output:
200013.000250020
result:
ok found '200013.0002500', expected '200013.0002500', error '0.0000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 7880kb
input:
1 1 6 -999999 2 999999 7 1 1 0 0 8 8
output:
8.485281374
result:
ok found '8.4852814', expected '8.4852814', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 8092kb
input:
1 1 10 -9999 9 9999 10 0 1 0 0 114 514
output:
516.514034066
result:
ok found '516.5140341', expected '516.5140341', error '0.0000000'
Test #12:
score: -100
Wrong Answer
time: 158ms
memory: 14172kb
input:
29 7 193 19 575 27 714 36 575 44 717 55 575 65 698 75 575 82 755 98 575 105 641 118 575 127 812 168 575 176 888 226 575 234 905 279 575 288 917 287 0 299 496 328 150 335 733 343 153 350 736 360 134 368 717 377 191 383 774 397 77 404 660 415 248 423 831 437 0 444 536 459 324 466 907 491 0 499 548 510...
output:
194.370779697
result:
wrong answer 1st numbers differ - expected: '434.2481536', found: '194.3707797', error = '0.5523970'