QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#95750 | #115. Fences | eyiigjkn | 41 | 6ms | 4116kb | C++14 | 3.1kb | 2023-04-11 19:45:51 | 2023-04-11 19:45:53 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
constexpr double INF=1e9;
int S,id[110][2];
double f[210][210];
struct Point
{
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
Point operator+(const Point &t)const{return Point(x+t.x,y+t.y);}
Point operator-(const Point &t)const{return Point(x-t.x,y-t.y);}
Point operator*(const double &t)const{return Point(x*t,y*t);}
double operator*(const Point &t)const{return x*t.x+y*t.y;}
Point operator/(const double &t)const{return Point(x/t,y/t);}
};
struct Seg
{
Point A,B;
Seg(){}
Seg(const Point &A,const Point &B):A(A),B(B){}
}a[110];
inline double Abs(const Point &t){return sqrt(t.x*t.x+t.y*t.y);}
inline void chkmin(double &x,const double &y){x=min(x,y);}
inline bool contain(const Point &A,const Point &B,const Point &C)
{
return C.x>=min(A.x,B.x) && C.x<=max(A.x,B.x) && C.y>=min(A.y,B.y) && C.y<=max(A.y,B.y);
}
inline Point geth(const Point &A,const Point &B,const Point &C)
{
auto D=(B-A)/Abs(B-A);
return A+D*((C-A)*D);
}
inline bool calc(const Point &A,const Point &B){return min(A.x,B.x)<0 && max(A.x,B.x)>=0 && min(A.y,B.y)>0;}
bool chk(const Point &A,const Point &B)
{
if((abs(A.x)<S && abs(A.y)<S) || (abs(B.x)<S && abs(B.y)<S)) return false;
if(A.x-A.y!=B.x-B.y)
{
double a=A.x*B.y-B.x*A.y,b=(B.y-B.x)-(A.y-A.x);
if(b<0) a=-a,b=-b;
if(a>=b*max(min(A.x,B.x),min(A.y,B.y)) && a<=b*min(max(A.x,B.x),max(A.y,B.y)) && abs(a)<b*S) return false;
}
if(A.x+A.y!=B.x+B.y)
{
double a=A.x*B.y-B.x*A.y,b=(B.x+B.y)-(A.x+A.y);
if(b<0) a=-a,b=-b;
if(a>=b*max(min(A.x,B.x),-max(A.y,B.y)) && a<=b*min(max(A.x,B.x),-min(A.y,B.y)) && abs(a)<b*S) return false;
}
return true;
}
pair<double,double> Dis(int i,int j)
{
double ans[2]={INF,INF};
for(auto P:{a[i].A,a[i].B})
for(auto Q:{a[j].A,a[j].B})
if(chk(P,Q))
chkmin(ans[calc(a[i].A,P)^calc(P,Q)^calc(Q,a[j].A)],Abs(P-Q));
for(auto P:{a[i].A,a[i].B})
{
auto Q=geth(a[j].A,a[j].B,P);
if(contain(a[j].A,a[j].B,Q) && chk(P,Q))
chkmin(ans[calc(a[i].A,P)^calc(P,Q)^calc(Q,a[j].A)],Abs(P-Q));
}
for(auto P:{a[j].A,a[j].B})
{
auto Q=geth(a[i].A,a[i].B,P);
if(contain(a[i].A,a[i].B,Q) && chk(P,Q))
chkmin(ans[calc(a[i].A,Q)^calc(Q,P)^calc(P,a[j].A)],Abs(P-Q));
}
return {ans[0],ans[1]};
}
int main()
{
int n,tot=0;
double ans=INF;
cin>>n>>S;
for(int i=1;i<=n;i++) scanf("%lf%lf%lf%lf",&a[i].A.x,&a[i].A.y,&a[i].B.x,&a[i].B.y);
for(int x:{S,-S})
for(int y:{S,-S})
a[++n]=Seg(Point(x,y),Point(x,y));
for(int i=1;i<=n;i++) id[i][0]=++tot,id[i][1]=++tot;
for(int i=1;i<=n;i++) f[id[i][0]][id[i][1]]=f[id[i][1]][id[i][0]]=INF;
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
{
double dis[2];
tie(dis[0],dis[1])=Dis(i,j);
for(int k:{0,1})
{
f[id[i][k]][id[j][k]]=f[id[j][k]][id[i][k]]=dis[0];
f[id[i][k]][id[j][k^1]]=f[id[j][k]][id[i][k^1]]=dis[1];
}
}
for(int k=1;k<=tot;k++)
for(int i=1;i<=tot;i++)
for(int j=1;j<=tot;j++)
chkmin(f[i][j],f[i][k]+f[k][j]);
for(int i=1;i<=n;i++) chkmin(ans,f[id[i][0]][id[i][1]]);
printf("%.4lf\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 18
Accepted
Test #1:
score: 18
Accepted
time: 2ms
memory: 3624kb
input:
1 20 -132 -148 7 -48
output:
160.0000
result:
ok found '160.00000', expected '160.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
1 40 40 81 118 181
output:
320.0000
result:
ok found '320.00000', expected '320.00000', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
1 60 -189 -95 -114 -101
output:
480.0000
result:
ok found '480.00000', expected '480.00000', error '0.00000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3680kb
input:
1 80 -17 134 -3 128
output:
640.0000
result:
ok found '640.00000', expected '640.00000', error '0.00000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
1 100 102 170 -78 186
output:
758.7768
result:
ok found '758.77680', expected '758.77677', error '0.00000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
1 120 111 175 178 151
output:
960.0000
result:
ok found '960.00000', expected '960.00000', error '0.00000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3832kb
input:
1 140 -25 -149 146 -188
output:
1000.8158
result:
ok found '1000.81580', expected '1000.81577', error '0.00000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1 160 -169 -113 -193 -168
output:
1260.1946
result:
ok found '1260.19460', expected '1260.19456', error '0.00000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3756kb
input:
1 170 -35 195 6 188
output:
1322.2801
result:
ok found '1322.28010', expected '1322.28015', error '0.00000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3792kb
input:
1 180 -198 -34 -198 169
output:
1248.2004
result:
ok found '1248.20040', expected '1248.20043', error '0.00000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
1 110 -136 64 -128 -130
output:
731.4613
result:
ok found '731.46130', expected '731.46132', error '0.00000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
1 130 156 -132 172 -71
output:
1011.3482
result:
ok found '1011.34820', expected '1011.34817', error '0.00000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
1 150 -193 -166 169 -185
output:
951.7755
result:
ok found '951.77550', expected '951.77547', error '0.00000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 170 174 43 196 168
output:
1258.9907
result:
ok found '1258.99070', expected '1258.99066', error '0.00000'
Test #15:
score: 0
Accepted
time: 2ms
memory: 3836kb
input:
1 190 83 -192 -106 -199
output:
1331.4995
result:
ok found '1331.49950', expected '1331.49946', error '0.00000'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3676kb
input:
1 150 -162 -155 198 -159
output:
913.5806
result:
ok found '913.58060', expected '913.58064', error '0.00000'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3632kb
input:
1 160 199 192 -200 185
output:
1016.9595
result:
ok found '1016.95950', expected '1016.95954', error '0.00000'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3628kb
input:
1 170 200 193 -200 195
output:
1067.9952
result:
ok found '1067.99520', expected '1067.99515', error '0.00000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
1 100 157 -148 58 -126
output:
794.6169
result:
ok found '794.61690', expected '794.61689', error '0.00000'
Test #20:
score: 0
Accepted
time: 2ms
memory: 3760kb
input:
1 50 -72 81 169 103
output:
374.4200
result:
ok found '374.42000', expected '374.42000', error '0.00000'
Subtask #2:
score: 23
Accepted
Dependency #1:
100%
Accepted
Test #21:
score: 23
Accepted
time: 0ms
memory: 3840kb
input:
3 50 -142 -144 -154 -165 -177 52 -97 -1 153 102 24 86
output:
400.0000
result:
ok found '400.00000', expected '400.00000', error '0.00000'
Test #22:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
6 100 -167 -90 -117 -148 18 114 119 180 -119 93 -147 -96 153 170 155 -192 -134 -100 142 -117 178 138 180 97
output:
200.7031
result:
ok found '200.70310', expected '200.70307', error '0.00000'
Test #23:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
6 150 -42 -198 111 -196 -54 -157 -179 -174 185 -166 -188 -183 45 199 -74 189 186 -192 -26 -185 49 181 173 193
output:
790.1660
result:
ok found '790.16600', expected '790.16595', error '0.00000'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
6 149 183 -198 -46 -173 194 112 191 43 171 -77 184 -79 -153 -154 -181 49 75 171 147 152 -161 187 -158 28
output:
666.0134
result:
ok found '666.01340', expected '666.01341', error '0.00000'
Test #25:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
6 145 168 190 199 -88 -177 -146 -173 -13 -142 -198 57 -148 -148 -22 -162 186 -113 -179 -58 -147 -114 151 19 168
output:
449.6510
result:
ok found '449.65100', expected '449.65102', error '0.00000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
6 134 -86 178 82 160 -199 -3 -169 -194 88 -185 -114 -168 143 -134 128 -155 52 -135 157 -178 -177 -114 -198 85
output:
577.6666
result:
ok found '577.66660', expected '577.66656', error '0.00000'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
6 121 111 -154 -94 -145 -165 -49 -200 -145 -156 -177 -180 -198 -133 195 -78 129 173 182 -6 137 173 -190 149 -42
output:
653.0941
result:
ok found '653.09410', expected '653.09414', error '0.00000'
Test #28:
score: 0
Accepted
time: 2ms
memory: 3856kb
input:
6 115 -118 73 -187 82 -10 140 -81 174 -74 -198 -24 -193 -131 -101 -86 -198 -125 -58 -167 10 111 -151 147 -97
output:
717.6152
result:
ok found '717.61520', expected '717.61523', error '0.00000'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
6 101 150 -14 105 -169 104 143 145 188 -166 -93 -199 148 -50 -134 -7 -200 194 -137 147 -145 132 -93 175 -21
output:
656.9653
result:
ok found '656.96530', expected '656.96533', error '0.00000'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
6 113 189 0 118 146 94 163 -67 176 -94 163 -186 29 -189 0 -118 -146 -94 -163 67 -176 94 -163 186 -29
output:
177.0646
result:
ok found '177.06460', expected '177.06458', error '0.00000'
Test #31:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
6 109 195 0 122 151 97 168 -69 182 -97 168 -192 30 -195 0 -122 -151 -97 -168 69 -182 97 -168 192 -30
output:
183.3740
result:
ok found '183.37400', expected '183.37402', error '0.00000'
Test #32:
score: 0
Accepted
time: 2ms
memory: 3632kb
input:
6 140 -183 -107 -182 148 159 -105 178 45 -171 147 49 153 193 70 111 182 182 -163 199 -48 -172 56 -133 -192
output:
436.5548
result:
ok found '436.55480', expected '436.55481', error '0.00000'
Test #33:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
6 131 181 190 -48 169 137 -171 189 125 -192 -87 -121 -192 -22 166 181 151 -147 151 -163 -56 -139 67 -125 200
output:
428.1397
result:
ok found '428.13970', expected '428.13974', error '0.00000'
Test #34:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
6 149 -99 -188 75 -155 -3 192 -180 178 155 189 187 -198 186 -19 161 167 -177 90 -194 -171 -151 167 -189 -185
output:
369.1587
result:
ok found '369.15870', expected '369.15867', error '0.00000'
Test #35:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
6 76 -184 41 -34 -150 163 -43 -55 -187 138 129 -154 185 -141 79 75 134 185 94 -45 99 -65 174 197 152
output:
218.4358
result:
ok found '218.43580', expected '218.43579', error '0.00000'
Test #36:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
6 98 -150 -132 198 -153 -101 -127 -151 124 -86 136 174 119 -92 193 164 122 -174 -162 -178 199 -151 -173 -161 168
output:
344.0948
result:
ok found '344.09480', expected '344.09478', error '0.00000'
Test #37:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
5 100 102 -127 -46 -164 -147 140 -102 196 177 93 73 115 200 -132 -74 -105 -150 187 -164 45
output:
607.0661
result:
ok found '607.06610', expected '607.06615', error '0.00000'
Test #38:
score: 0
Accepted
time: 2ms
memory: 3864kb
input:
2 100 179 9 84 -177 -105 -138 -150 -153
output:
719.9690
result:
ok found '719.96900', expected '719.96904', error '0.00000'
Test #39:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
5 50 -50 -165 167 -56 196 46 -17 -115 -61 -45 -150 -97 177 35 -98 84 -119 32 -168 5
output:
199.4866
result:
ok found '199.48660', expected '199.48662', error '0.00000'
Test #40:
score: 0
Accepted
time: 2ms
memory: 3788kb
input:
2 50 122 62 -37 171 -52 -57 -50 -126
output:
400.0000
result:
ok found '400.00000', expected '400.00000', error '0.00000'
Test #41:
score: 0
Accepted
time: 2ms
memory: 3868kb
input:
2 100 101 101 -101 101 -101 -101 -101 101
output:
402.0000
result:
ok found '402.00000', expected '402.00000', error '0.00000'
Test #42:
score: 0
Accepted
time: 2ms
memory: 3580kb
input:
3 96 0 -97 97 -97 0 97 97 97 97 -97 97 97
output:
384.0104
result:
ok found '384.01040', expected '384.01042', error '0.00000'
Test #43:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
4 96 97 97 -97 97 -97 -97 -97 97 -97 -97 97 -97 97 97 97 -97
output:
0.0000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Subtask #3:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #44:
score: 0
Wrong Answer
time: 6ms
memory: 4116kb
input:
100 10 -104 -49 -183 -123 -63 103 -60 31 83 172 100 -55 -79 -88 51 -45 17 60 -140 151 14 58 -91 -22 162 150 199 -174 -190 -2 -196 116 141 64 162 85 69 -192 141 86 19 62 16 69 -166 193 93 5 -191 -154 55 -190 -93 -154 35 -77 134 173 116 29 83 -1 93 -67 -145 -61 -124 25 162 -180 124 -124 -113 -189 146 ...
output:
18.2906
result:
wrong answer 1st numbers differ - expected: '19.74659', found: '18.29060', error = '0.07373'