QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#485739#8082. Minimum Euclidean DistanceztttttWA 122ms4108kbC++234.7kb2024-07-21 03:41:172024-07-21 03:41:18

Judging History

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

  • [2024-07-21 03:41:18]
  • 评测
  • 测评结果:WA
  • 用时:122ms
  • 内存:4108kb
  • [2024-07-21 03:41:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5010;
double aa[N],bb[N],cc[N];
pair<double,double>p[N];
//struct S}{
//	int x1,y1,x2,y1;
//}s[N];
double xx[N],yy[N];
signed main(){
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>p[i].first>>p[i].second;
	}
	for(int i=2;i<=n;i++){
		xx[i]=p[i].first-p[i-1].first;
	}
	xx[1]=p[1].first-p[n].first;
	//for(int i=1;i<=n;i++)cout<<i<<" "<<xx[i]<<endl;
	for(int i=2;i<=n;i++){
		yy[i]=p[i].second-p[i-1].second;
	}
	yy[1]=p[1].second-p[n].second;
	//for(int i=1;i<=n;i++)cout<<i<<" "<<yy[i]<<endl;
	for(int i=2;i<=n;i++){
		aa[i]=p[i].second-p[i-1].second;
		bb[i]=p[i-1].first-p[i].first;
		cc[i]=p[i].first*p[i-1].second-p[i-1].first*p[i].second; 
	}
	aa[1]=p[1].second-p[n].second; 
	bb[1]=p[n].first-p[1].first;
	cc[1]=p[1].first*p[n].second-p[n].first*p[1].second;
//	for(int i=2;i<=n;i++){
//		bb[i]=p[i-1].second-xl[i]*p[i-1].first;
//	}
//	bb[1]=p[n].second-xl[1]*p[n].first;
	for(int i=1;i<=q;i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		double r=0.5*sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
		//cout<<r<<endl;
		double yxx=(x1+x2)*0.5;
		//cout<<yxx<<endl;
		double yxy=(y1+y2)*0.5;
		//cout<<yxy<<endl;
		int cntl=0,cntz=0,cntf=0;
		for(int j=1;j<n;j++){
			double xlx=yxx-p[j].first;
//			cout<<j<<" "<<p[j].first<<endl;
//			cout<<j<<" "<<yxx<<endl;
//			cout<<j<<" "<<xlx<<endl;
			double xly=yxy-p[j].second;
			double cj=xx[j+1]*xly-yy[j+1]*xlx; 
		//	cout<<j<<" "<<cj<<endl;
			if(cj<0){
				cntf++;
			}else if(cj>0){
				cntz++;
			}else{
				cntl++;
			}
		}
		//cout<<cntf<<" "<<cntl<<" "<<cntz<<endl;
		double xlx=yxx-p[n].first;
		double xly=yxy-p[n].second;
		double cj=xx[1]*xly-yy[1]*xlx;
		if(cj<0){
				cntf++;
			}else if(cj>0){
				cntz++;
			}else{
				cntl++;
			}
		if(cntl>0){
			cout<<fixed<<setprecision(9);
			cout<<0.5*r*r<<endl; 
		}else if(cntz==n){
			cout<<fixed<<setprecision(9);
			cout<<0.5*r*r<<endl; 
		}else{
			double jl=100000000;
//			for(int j=1;j<=n;j++){
//				jl=min(jl,sqrt((yxx-p[j].first)*(yxx-p[j].first)+(yxy-p[j].second)*(yxy-p[j].second)));
//			}
//			for(int j=1;j<=n;j++){
//				jl=min(jl,)
//			} 
int flag=0;
            for(int j=2;j<=n;j++){
            	double aaa=bb[j],bbb=-aa[j];
            	double ccc=aa[j]*yxy-bb[j]*yxx;
            	double jdx=1.0*(-cc[j]*bbb+bb[j]*ccc)/(aa[j]*bbb-bb[j]*aaa); 
            	double jdy=1.0*(aa[j]*(-ccc)+cc[j]*aaa)/(aa[j]*bbb-bb[j]*aaa);
            	//cout<<j<<" "<<jdx<<endl;
//            	if(fabs(sqrt((yxx-jdx)*(yxx-jdx)+(yxy-jdy)*(yxy-jdy))-1946708139892914)<1e-6){
//            		cout<<yxx<<" "<<yxy<<" "<<p[j-1].first<<" "<<p[j-1].second<<" "<<p[j].first<<" "<<p[j].second<<" "<<jdx<<" "<<jdy<<endl;
//            		flag=1;
//				}
            	if((jdx>min(p[j-1].first,p[j].first)||fabs(jdx-min(p[j-1].first,p[j].first))<1e-6)&&(jdx<max(p[j-1].first,p[j].first)||fabs(jdx-max(p[j-1].first,p[j].first))<1e-6)&&(jdy>min(p[j-1].second,p[j].second)||fabs(jdy-min(p[j-1].second,p[j].second))<1e-6)&&(jdy<max(p[j-1].second,p[j].second)||fabs(jdy-max(p[j-1].second,p[j].second))<1e-6)){
            		jl=min(jl,sqrt((yxx-jdx)*(yxx-jdx)+(yxy-jdy)*(yxy-jdy)));
//            		if(fabs(jl-1946966666535562.75)<1e-6){
//            			cout<<yxx<<" "<<yxy<<" "<<p[j-1].first<<" "<<p[j-1].second<<" "<<p[j].first<<" "<<p[j].second<<" "<<jdx<<" "<<jdy<<endl;
//            			flag=1;
//            			break;
//					}
				}
			}
			if(flag)continue;
			double aaa=bb[1],bbb=-aa[1];
            	double ccc=aa[1]*yxy-bb[1]*yxx;
            	double jdx=1.0*(-cc[1]*bbb+bb[1]*ccc)/(aa[1]*bbb-bb[1]*aaa); 
            	double jdy=1.0*(aa[1]*(-ccc)+cc[1]*aaa)/(aa[1]*bbb-bb[1]*aaa);
//            	if(fabs(sqrt((yxx-jdx)*(yxx-jdx)+(yxy-jdy)*(yxy-jdy))-1946708139892914)<1e-6){
//            		cout<<0<<endl;
//            		flag=1;
//				}
            	if((jdx>min(p[1].first,p[n].first)||fabs(jdx-min(p[1].first,p[n].first))<1e-6)&&(jdx<max(p[1].first,p[n].first)||fabs(jdx-max(p[1].first,p[n].first))<1e-6)&&(jdy>min(p[1].second,p[n].second)||fabs(jdy-min(p[1].second,p[n].second))<1e-6)&&(jdy<max(p[1].second,p[n].second)||fabs(jdy-max(p[1].second,p[n].second))<1e-6)){
            		jl=min(jl,sqrt((yxx-jdx)*(yxx-jdx)+(yxy-jdy)*(yxy-jdy)));
//            		if(fabs(jl-1946966666535562.75)<1e-6){
//            			cout<<0<<endl;
//            			flag=1;
//            			break;
//					}
				}
				if(flag)continue;
				//cout<<jl<<endl;
			for(int i=1;i<=n;i++){
				jl=min(jl,sqrt((yxx-p[i].first)*(yxx-p[i].first)+(yxy-p[i].second)*(yxy-p[i].second)));
			}
//			if(fabs(0.5*r*r+jl*jl-1946966666535993)<1e-6){
//				cout<<0.5*r*r<<endl;
//				continue;
//			}
			cout<<0.5*r*r+jl*jl<<endl;
		}
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3928kb

input:

4 3
0 0
1 0
1 1
0 1
0 0 1 1
1 1 2 2
1 1 2 3

output:

0.250000000
0.750000000
1.875000000

result:

ok Your answer is acceptable!^ ^

Test #2:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

48 10
-30 0
-29 -4
-28 -7
-27 -9
-25 -12
-22 -16
-21 -17
-17 -20
-14 -22
-12 -23
-9 -24
-5 -25
-4 -25
0 -24
3 -23
5 -22
8 -20
12 -17
13 -16
16 -12
18 -9
19 -7
20 -4
21 0
21 1
20 5
19 8
18 10
16 13
13 17
12 18
8 21
5 23
3 24
0 25
-4 26
-5 26
-9 25
-12 24
-14 23
-17 21
-21 18
-22 17
-25 13
-27 10
-28 ...

output:

589.5
51.4706
1051.250000000
66.625000000
174.125000000
562.675000000
272.394230769
287.385000000
689.625000000
436.250000000

result:

ok Your answer is acceptable!^ ^

Test #3:

score: -100
Wrong Answer
time: 122ms
memory: 4108kb

input:

5000 5000
-50000000 0
-49999885 -49450
-49999770 -85675
-49999604 -122394
-49999391 -157604
-49999130 -192731
-49998803 -229143
-49998399 -267196
-49997956 -303872
-49997469 -339362
-49996891 -377221
-49996257 -414903
-49995577 -451819
-49994843 -488600
-49994059 -524941
-49993173 -563137
-49992252 ...

output:

2.21479e+15
1.63265e+15
3.95474e+15
5.40511e+15
8.17275e+14
9.02261e+14
3194363161448624.000000000
1619744446324385.000000000
363457485421825.187500000
4776425533214309.000000000
8267595460255074.000000000
2467163193204921.500000000
1182580285938702.250000000
1785755073284987.000000000
2070106793477...

result:

wrong answer Except 11553906067411116.000000000000, but found 10000000000000420.000000000000!QAQ