QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#636417 | #9455. Getting Lost | ucup-team3586# | WA | 5ms | 4628kb | C++23 | 8.8kb | 2024-10-12 23:49:17 | 2024-10-12 23:49:17 |
Judging History
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'