QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#95875 | #115. Fences | tricyzhkx | 0 | 3ms | 3872kb | C++14 | 2.8kb | 2023-04-12 11:07:50 | 2023-04-12 11:07:52 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
const double eps=1e-8,INF=1e9;
struct Point
{
double x,y;
Point(double _x=0,double _y=0):x(_x),y(_y){}
Point operator+(const Point &a)const{return Point(x+a.x,y+a.y);}
Point operator-(const Point &a)const{return Point(x-a.x,y-a.y);}
Point operator*(double k)const{return Point(x*k,y*k);}
double operator*(const Point &a)const{return x*a.x+y*a.y;}
double operator^(const Point &a)const{return x*a.y-y*a.x;}
bool operator==(const Point &a)const{return fabs(x-a.x)<eps && fabs(y-a.y)<eps;}
};
struct Line
{
Point A,B;
Line(Point P=0):A(P),B(P){}
}L[110];
int n,S;
double dis[210][210];
void upd(double &a,double b){a=min(a,b);}
bool check(Point a){return max(fabs(a.x),fabs(a.y))>=S;}
bool onSeg(double x1,double x2,double x){return min(x1,x2)<=x && x<=max(x1,x2);}
bool onSeg(Point A,Point B,Point C){return onSeg(A.x,B.x,C.x) && onSeg(A.y,B.y,C.y);}
double sq(double x){return x*x;}
double dist2(Point A,Point B=0){return sq(A.x-B.x)+sq(A.y-B.y);}
double dist(Point A,Point B=0){return sqrt(dist2(A,B));}
bool check(Point A,Point B)
{
if(!check(A) || !check(B)) return false;
if(A==B) return true;
double dx=A.x-B.x,dy=A.y-B.y;
if(fabs(dx-dy)>eps)
{
double k=(A.x-A.y)/(dy-dx),x=A.x+k*dx,y=A.y+k*dy;
if(onSeg(A,B,Point(x,y)) && !check(Point(x,y))) return false;
}
if(fabs(dx+dy)>eps)
{
double k=-(A.x+A.y)/(dx+dy),x=A.x+k*dx,y=A.y+k*dy;
if(onSeg(A,B,Point(x,y)) && !check(Point(x,y))) return false;
}
return true;
}
int inter(Point A,Point B)
{
if((A.x<0 && B.x<0) || (A.x>=0 && B.x>=0)) return 0;
if(A.x>B.x) swap(A,B);
return ((Point()-A)^(B-A))>0;
}
void W(int i,int j)
{
auto U=[&](int t,double d){for(int k=0;k<2;k++) upd(dis[2*i-k][2*j-(k^t)],d);};
auto calc=[&](Point A,Point B){return inter(L[i].A,A)^inter(A,B)^inter(B,L[j].A);};
for(Point A:{L[i].A,L[i].B})
for(Point B:{L[j].A,L[j].B})
if(check(A,B)) U(calc(A,B),dist(A,B));
if(L[i].A==L[i].B || L[j].A==L[j].B) return;
for(Point A:{L[i].A,L[i].B})
{
Point P0=L[j].A,a=A-P0,b=L[j].B-P0,P=P0+b*(a*b/dist2(b));
if(onSeg(L[j].A,L[j].B,P) && check(A,P)) U(calc(A,P),dist(A,P));
}
for(Point A:{L[j].A,L[j].B})
{
Point P0=L[i].A,a=A-P0,b=L[i].B-P0,P=P0+b*(a*b/dist2(b));
if(onSeg(L[i].A,L[i].B,P) && check(A,P)) U(calc(P,A),dist(A,P));
}
}
int main()
{
cin>>n>>S;
for(int i=1;i<=n;i++) scanf("%lf%lf%lf%lf",&L[i].A.x,&L[i].A.y,&L[i].B.x,&L[i].B.y);
for(int x:{-S,S})
for(int y:{-S,S})
L[++n]=Line(Point(x,y));
for(int i=1;i<=2*n;i++) fill(dis[i]+1,dis[i]+2*n+1,INF);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
W(i,j);
for(int k=1;k<=2*n;k++)
for(int i=1;i<=2*n;i++)
for(int j=1;j<=2*n;j++)
upd(dis[i][j],dis[i][k]+dis[k][j]);
double ans=INF;
for(int i=1;i<=n;i++) upd(ans,dis[2*i-1][2*i]);
printf("%.10lf\n",ans);
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 18
Accepted
time: 2ms
memory: 3608kb
input:
1 20 -132 -148 7 -48
output:
160.0000000000
result:
ok found '160.00000', expected '160.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
1 40 40 81 118 181
output:
320.0000000000
result:
ok found '320.00000', expected '320.00000', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
1 60 -189 -95 -114 -101
output:
480.0000000000
result:
ok found '480.00000', expected '480.00000', error '0.00000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
1 80 -17 134 -3 128
output:
640.0000000000
result:
ok found '640.00000', expected '640.00000', error '0.00000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
1 100 102 170 -78 186
output:
758.7767713905
result:
ok found '758.77677', expected '758.77677', error '0.00000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
1 120 111 175 178 151
output:
960.0000000000
result:
ok found '960.00000', expected '960.00000', error '0.00000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3580kb
input:
1 140 -25 -149 146 -188
output:
1003.4065097713
result:
ok found '1003.40651', expected '1000.81577', error '0.00259'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
1 160 -169 -113 -193 -168
output:
1266.2389512834
result:
ok found '1266.23895', expected '1260.19456', error '0.00480'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
1 170 -35 195 6 188
output:
1322.2801499666
result:
ok found '1322.28015', expected '1322.28015', error '0.00000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3872kb
input:
1 180 -198 -34 -198 169
output:
1248.2004274972
result:
ok found '1248.20043', expected '1248.20043', error '0.00000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
1 110 -136 64 -128 -130
output:
731.6782370645
result:
ok found '731.67824', expected '731.46132', error '0.00030'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3612kb
input:
1 130 156 -132 172 -71
output:
1011.3481724253
result:
ok found '1011.34817', expected '1011.34817', error '0.00000'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3628kb
input:
1 150 -193 -166 169 -185
output:
954.4505869906
result:
ok found '954.45059', expected '951.77547', error '0.00281'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3612kb
input:
1 170 174 43 196 168
output:
1259.1143649954
result:
ok found '1259.11436', expected '1258.99066', error '0.00010'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1 190 83 -192 -106 -199
output:
1331.4994569984
result:
ok found '1331.49946', expected '1331.49946', error '0.00000'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
1 150 -162 -155 198 -159
output:
917.9419064359
result:
ok found '917.94191', expected '913.58064', error '0.00477'
Test #17:
score: 0
Accepted
time: 3ms
memory: 3684kb
input:
1 160 199 192 -200 185
output:
1021.4650210755
result:
ok found '1021.46502', expected '1016.95954', error '0.00443'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3632kb
input:
1 170 200 193 -200 195
output:
1070.4683613871
result:
ok found '1070.46836', expected '1067.99515', error '0.00232'
Test #19:
score: 0
Accepted
time: 2ms
memory: 3676kb
input:
1 100 157 -148 58 -126
output:
800.0000000000
result:
ok found '800.00000', expected '794.61689', error '0.00677'
Test #20:
score: -18
Wrong Answer
time: 2ms
memory: 3756kb
input:
1 50 -72 81 169 103
output:
400.0000000000
result:
wrong answer 1st numbers differ - expected: '374.42000', found: '400.00000', error = '0.06832'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%