QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#636417#9455. Getting Lostucup-team3586#WA 5ms4628kbC++238.8kb2024-10-12 23:49:172024-10-12 23:49:17

Judging History

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

  • [2024-10-12 23:49:17]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:4628kb
  • [2024-10-12 23:49:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

namespace HaitangSuki
{
// 定义点和线段结构体
struct Point {
    double x, y;
};

struct LineSegment {
    Point p1, p2;
};

// 计算两点之间的距离
double distance(Point p1, Point p2) {
    return sqrt(pow(p2.x - p1.x, 2) + pow(p2.y - p1.y, 2));
}

// 计算点到线段的距离
double distanceToLineSegment(Point p, LineSegment l) {
    double len = distance(l.p1, l.p2);
    if (len <1e-8) { // 线段长度为0,即线段为点
        return distance(p, l.p1);
    }
    double r = ((p.x - l.p1.x) * (l.p2.x - l.p1.x) + (p.y - l.p1.y) * (l.p2.y - l.p1.y)) / pow(len, 2);
    if (r <= 0) { // 垂足在p1处
        return distance(p, l.p1);
    } else if (r >= 1) { // 垂足在p2处
        return distance(p, l.p2);
    } else { // 垂足在线段上
        Point foot = { l.p1.x + r * (l.p2.x - l.p1.x), l.p1.y + r * (l.p2.y - l.p1.y) };
        return distance(p, foot);
    }
}

double main(double x1,double y1,double x2,double y2,double x3,double y3) {
    Point p = { x1,y1 };
    LineSegment l = { { x2, y2 }, { x3, y3 } };

    double dist = distanceToLineSegment(p, l);
    return dist;
}
}

const double eps = 1e-7;
const double PI = acos(-1.0), pi=acos(-1.0);
int sgn(double x){
    if(fabs(x) < eps)return 0;
    if(x < 0)return-1;
    else return 1;
}
double sqr(double x){return x*x;}
struct Point{
    double x, y;
Point(){}
    Point(double _x,double _y){
        x = _x;
        y = _y;
    }
    bool operator == (Point b)const{
        return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;
    }
    bool operator < (Point b)const{
        return sgn(x-b.x)== 0-sgn(y-b.y)?0:x<b.x;
    }
    Point operator-(const Point &b)const{
        return Point(x-b.x,y-b.y);
    }
    //叉积
    double operator ^(const Point &b)const{
        return x*b.y-y*b.x;
    }
    //点积
    double operator *(const Point &b)const{
        return x*b.x + y*b.y;
    }
    //返回长度
    double len(){
        return hypot(x,y);//库函数
    }
    //返回长度的平方
    double len2(){
        return x*x + y*y;
    }
    //返回两点的距离
    double distance(Point p){
        return hypot(x-p.x,y-p.y);
    }
    Point operator +(const Point &b)const{
        return Point(x+b.x,y+b.y);
    }
    Point operator *(const double &k)const{
        return Point(x*k,y*k);
    }
    Point operator /(const double &k)const{
        return Point(x/k,y/k);
    }
};
  
struct Line{
    Point s,e;
Line(){}
    Line(Point _s,Point _e){
        s = _s;
        e = _e;
    }
      
    //求线段长度
    double length(){
        return s.distance(e);
    }
   
    double dispointtoline(Point p){
        return fabs((p-s)^(e-s))/length();
    }
};
struct Circle{
    Point p;
    double r;
Circle(){}
    Circle(Point _p,double _r){
        p = _p;
        r = _r;
    }
    // 过一点知道角度和距离 求另一点 
    Point GP(double b) { 
        return Point(p.x + cos(b)*r, p.y+sin(b)*r);
    }
      
    int relationline(Line v){
        double dst = v.dispointtoline(p);
        if(sgn(dst-r) < 0)return 2;
        else if(sgn(dst-r) == 0)return 1;
        return 0;
    }
}CC[200],C1,C2;;
 
const double Pi=acos(-1.0);
 
struct Intersect{
    Point P[2];
   bool operator <(const Intersect &rtm) const{
       return sgn(P[0].x-rtm.P[0].x)<0||(sgn(P[0].x-rtm.P[0].x)==0&&sgn(P[0].y-rtm.P[0].y)<0);
   }
}ANS[7];
 
typedef Point Vector;
 
double GPA(Vector A){//Get_Polar_Angle
    return atan2(A.y,A.x);
}
double GL(Vector A){//Get_Length
   return sqrt(A*A);
}
//求公切线,这个模板都没问题
int GCCI(Circle A,Circle B){//Get_Circle_Circle_Intersection
    int cnt=0,a=0,b=1;
    if(A.r<B.r) swap(A,B),swap(a,b);
    Vector u=B.p-A.p;
    double d=GL(u),rdec=A.r-B.r,radd=A.r+B.r;
    if(sgn(d-rdec)<0) return 0;                 //内含
    if(sgn(d)==0&&A.r==B.r) {
        ANS[1].P[a] = A.p;
        ANS[1].P[b] = A.GP(PI);
        return 1;             //重合,无线多,原本返回-1,但这题特殊
                             
                            }
    double base=GPA(u);
    if(sgn(d-rdec)==0){                            //内切
        ANS[++cnt].P[a]=A.GP(base); ANS[cnt].P[b]=B.GP(base);
        return cnt;
    }
    double da=acos((A.r-B.r)/d);                    //2条外公切线
    ANS[++cnt].P[a]=A.GP(base+da); ANS[cnt].P[b]=B.GP(base+da);
    ANS[++cnt].P[a]=A.GP(base-da); ANS[cnt].P[b]=B.GP(base-da);
    if(sgn(d-radd)==0){                            //1条内公切线
        ANS[++cnt].P[a]=A.GP(base); ANS[cnt].P[b]=B.GP(base+Pi);
    }
    else if(sgn(d-radd)>0){                     //2条内公切线
        da=acos((A.r+B.r)/d);
        ANS[++cnt].P[a]=A.GP(base+da); ANS[cnt].P[b]=B.GP(base+da+Pi);
        ANS[++cnt].P[a]=A.GP(base-da); ANS[cnt].P[b]=B.GP(base-da+Pi);
    }
    return cnt;
}
// #define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
#define pdd pair<double,double>
pdd to_Point(Point o){return make_pair(o.x,o.y);}
pdd a[603];
int bel[603];
double d[603][603];
double dist(pdd x,pdd y)
{
	double A=x.first-y.first;
	double B=x.second-y.second;
	return sqrt(A*A+B*B);
}
double x[603],y[603],r[603];
signed main()
{
	for(int T=read();T--;)
	{
		int n=read(),m=0;
		int sx=read(),sy=read();
		for(int i=0; i<=n; ++i)
			x[i]=read(),y[i]=read(),r[i]=read();
		x[++n]=sx,y[n]=sy,r[n]=0;
		a[0]={sx,sy};
		bel[0]=n;
		map<pdd,int> mp; 
		int nn=n-1;
		for(int i=1; i<=nn; ++i)
		{
			int j=0;
			if(dist(make_pair(x[i],y[i]),make_pair(x[j],y[j]))<=r[i])
			{
				auto A=make_pair(x[j]-x[i],y[j]-y[i]);
				swap(A.first,A.second);
				A.first*=-1;
				x[++n]=A.first+x[0];
				y[n]=A.second+y[0];
				r[n]=0;
			// puts("create");
			// cout<<x[n]<<" "<<y[n]<<" "<<r[n]<<endl;
					A.first*=-1;
					A.second*=-1;
				x[++n]=A.first+x[0];
				y[n]=A.second+y[0];
				r[n]=0;
				continue;
			}
			int sz=GCCI(Circle(Point(x[i],y[i]),r[i]),
				Circle(Point(x[j],y[j]),0));
			for(int oo=1; oo<=sz; ++oo){
			auto A=to_Point(ANS[oo].P[1]);
			auto B=to_Point(ANS[oo].P[0]);
			auto C=make_pair(B.first-A.first,B.second-A.second);
			double lC=sqrt(C.first*C.first+C.second*C.second);
			double mul=r[0]/lC;
			x[++n]=C.first*mul+A.first;
			y[n]=C.second*mul+A.second;
			r[n]=0;

			}
		}
		x[++n]=x[0],y[n]=y[0],r[n]=0;
		for(int i=1; i<=n; ++i)
			for(int j=i+1; j<=n; ++j)
			{
				int sz=GCCI(Circle(Point(x[i],y[i]),r[i]),
				Circle(Point(x[j],y[j]),r[j]));
				for(int k=1; k<=sz; ++k)
				{
					a[++m]=to_Point(ANS[k].P[0]);
					mp[a[m]]=i;
					a[++m]=to_Point(ANS[k].P[1]);
					mp[a[m]]=j;
				}
			}
		// cout<<m<<endl;
		sort(a+1,a+m+1);
		m=unique(a+1,a+m+1)-a-1;
		for(int i=1; i<=m; ++i)
		{
			bel[i]=mp[a[i]];
			// printf("%d %.2lf %.2lf\n",bel[i],a[i].first,a[i].second);
		}
		// cout<<m<<endl;
		// return 0;
		double ans=1e18;
		for(int i=0; i<=m; ++i)
			for(int j=i+1; j<=m; ++j)
			{
				if(fabs(a[i].first-a[j].first)<1e-7&&
				fabs(a[i].second-a[j].second)<1e-7)
				{
					d[i][j]=0;
					d[j][i]=0;
					continue;
				}
				if(bel[i]==bel[j])
				{
					int id=bel[i];
					double a1=atan2(a[i].second-y[id],a[i].first-x[id]);
					double a2=atan2(a[j].second-y[id],a[j].first-x[id]);
					double b1=fabs(a1-a2);
					double b2=pi*2-b1;
					// cout<<b1<<" "<<b2<<endl;
					double b=min(b1,b2);
					d[i][j]=d[j][i]=b*r[id];
					// cout<<d[i][j]<<endl;
					// cout<<dist(a[i],a[j])<<endl;
					// printf("C %d %d\n",i,j);
				}
				else
				{
					bool boom=0;
					for(int k=1; k<n; ++k)
					{
						if(HaitangSuki::main(x[k],y[k],
						a[i].first,a[i].second,
						a[j].first,a[j].second
						)<r[k]-1e-7)
						{
							boom=1;
							break;
						}
					}
					if(boom) d[i][j]=d[j][i]=1e18;
					else d[i][j]=d[j][i]=dist(a[i],a[j]);
					// if(d[i][j]<1e17) printf("I %d %d\n",i,j);
				}
			}
		for(int i=0; i<=m; ++i)
			for(int j=0; j<=m; ++j)
				for(int k=0; k<=m; ++k)
					d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
		a[m+1]={x[0],y[0]};
		for(int i=0; i<=m; ++i)
		{
			int j=m+1;
			if(fabs(a[i].first-a[j].first)<1e-7&&
				fabs(a[i].second-a[j].second)<1e-7)
				{
					ans=min(ans,d[0][i]);
					continue;
				}
					bool boom=0;
					for(int k=1; k<n; ++k)
					{
						if(HaitangSuki::main(x[k],y[k],
						a[i].first,a[i].second,
						a[j].first,a[j].second
						)<r[k]-1e-7)
						{
							boom=1;
							break;
						}
					}
					if(!boom)
					{
						// cout<<"OK"<<i<<endl;
						double Z=dist(a[j],a[i]);
						ans=min(ans,d[0][i]+max(0.0,Z-r[0]));
					}
		}
		printf("%.10lf\n",ans);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
1
10 0
0 0 2
6 0 1
0
0 10
0 0 5

output:

8.2091914637
5.0000000000

result:

ok 2 numbers

Test #2:

score: -100
Wrong Answer
time: 5ms
memory: 4628kb

input:

52
0
0 10
0 0 5
0
10 0
0 0 5
1
10 0
0 0 2
6 0 1
1
10 0
4 0 2
6 0 1
1
10 0
3 0 4
6 0 2
1
10 0
3 0 2
6 0 3
1
10 0
3 0 4
6 0 3
2
10 0
-2 0 4
6 4 3
6 -4 3
2
10 0
-2 0 7
6 4 3
6 -4 3
2
10 6
-2 0 7
6 4 3
6 -4 3
2
10 2
-2 0 14
6 4 3
6 -4 3
2
14 4
-2 0 14
6 4 3
6 -4 3
2
12 -10
-2 0 14
2 2 3
6 -4 3
2
8 -8
-2...

output:

5.0000000000
5.0000000000
8.2091914637
4.3936127938
4.8228688993
9.1899375480
8.1899375480
8.0000000000
5.0000000000
7.9748397697
1.9204552211
3.1180204348
4.3045129884
2.1201247349
6.5188134573
5.7291376167
2.0000000000
51.8641407784
87.0964188128
54.2441597114
11.6619037897
35.7376565482
11.180339...

result:

wrong answer 6th numbers differ - expected: '8.3743109', found: '9.1899375', error = '0.0973963'