QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#95875#115. Fencestricyzhkx0 3ms3872kbC++142.8kb2023-04-12 11:07:502023-04-12 11:07:52

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-12 11:07:52]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:3872kb
  • [2023-04-12 11:07:50]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

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%