QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#95750#115. Fenceseyiigjkn41 6ms4116kbC++143.1kb2023-04-11 19:45:512023-04-11 19:45:53

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-11 19:45:53]
  • 评测
  • 测评结果:41
  • 用时:6ms
  • 内存:4116kb
  • [2023-04-11 19:45:51]
  • 提交

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;
}

詳細信息

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'