QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#753258 | #6734. Click the Circle | XfJbUhpyzgaW | WA | 1ms | 5900kb | C++17 | 3.6kb | 2024-11-16 12:01:52 | 2024-11-16 12:01:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define double long double
const double eps = 1e-9;
struct node{
double sx,sy,tx,ty,u,v;
int type,id;
// 1 - moving circle
// 2 - boundary
}a[4005];
double R,d;
int n,m=0;
double sqr(double x){return x*x;}
double dis(double x,double y,node it){
double d1=sqr(x-it.sx) + sqr(y-it.sy),
d2=sqr(x-it.tx) + sqr(y-it.ty);
if (it.sx==it.tx && it.sy==it.ty) return min(d1,d2);
double t= - ((it.sx-x)*(it.tx-it.sx)+ (it.sy-y)*(it.ty-it.sy) ) / (sqr(it.tx-it.sx) + sqr(it.ty-it.sy));
if (t<0 || t>1) return min(d1,d2);
double ix=(1-t)*it.sx+t*it.tx,iy=(1-t)*it.sy+t*it.ty;
return sqr(x-ix)+sqr(y-iy);
}
bool check(node it1,node it2){
if (it1.type==1 && it2.type==1){
// printf(" /1/ ");
// d^2 = a t^2 + b t + c
double u=max(it1.u,it2.u),v=min(it1.v,it2.v);
if (u>v) return 0;
double v1x=(it1.tx-it1.sx)/(it1.v-it1.u),
v1y=(it1.ty-it1.sy)/(it1.v-it1.u),
v2x=(it2.tx-it2.sx)/(it2.v-it2.u),
v2y=(it2.ty-it2.sy)/(it2.v-it2.u);
it1.sx+=v1x*(u-it1.u),it1.sy+=v1y*(u-it1.u),
it2.sx+=v2x*(u-it2.u),it2.sy+=v2y*(u-it2.u);
double a = sqr (v1x-v2x)+sqr(v1y-v2y) ,
b = 2*(it1.sx-it2.sx)*(v1x-v2x) + 2*(it1.sy-it2.sy)*(v1y-v2y),
c = sqr(it1.sx-it2.sx) + sqr(it1.sy-it2.sy);
double T = v-u,t0 = -b/(2*a);
double d1 = c ,
d2 = a * T * T + b * T + c,
d3 = 0<=t0 && t0<=T ? a * t0 * t0 + b * t0 + c : 1e18;
double d=min({d1,d2,d3});
return d<=4*R*R+eps;
}
if (it2.type == 1) swap(it1, it2);
double u=max(it1.u,it2.u),v=min(it1.v,it2.v);
if (u>v) return 0;
// two boundaries intersect
double l=0,r=1.0,ans=1e18;
if (it1.type == 1) {
l = (it1.u - u) / (v - u);
r = (it1.v - u) / (v - u);
}
while (fabs(r-l)>eps){
double m1=(2*l+r)/3,m2=(l+2*r)/3;
double x1=(1-m1)*it1.sx+m1*it1.tx,
y1=(1-m1)*it1.sy+m1*it1.ty,
x2=(1-m2)*it1.sx+m2*it1.tx,
y2=(1-m2)*it1.sy+m2*it1.ty;
double d1=dis(x1,y1,it2),d2=dis(x2,y2,it2);
if (d1>d2) l=m1,ans=d2;
else r=m2,ans=d1;
}
// printf("%.10lf ", ans);
return ans<=4*R*R+eps;
}
int buc[2100][2100];
int main(){
// freopen("t.in","r",stdin);
scanf("%d%Lf%Lf",&n,&R,&d);
int ans=0;
for (int tp,i=1;i<=n;++i){
scanf("%d",&tp);
if (tp==1){
double x,y,t;
scanf("%Lf%Lf%Lf",&x,&y,&t);
++m;a[m].sx=a[m].tx=x,a[m].sy=a[m].ty=y,a[m].u=t-d,a[m].v=t+d,a[m].type=1,a[m].id=i;
}
else{
double sx,sy,tx,ty,u,v;
scanf("%Lf%Lf%Lf%Lf%Lf%Lf",&sx,&sy,&tx,&ty,&u,&v);
++m;a[m].sx=a[m].tx=sx,a[m].sy=a[m].ty=sy,a[m].u=u-d,a[m].v=u-eps,a[m].type=1,a[m].id=i;
++m;a[m].sx=sx,a[m].sy=sy,a[m].tx=tx,a[m].ty=ty,a[m].u=u,a[m].v=v,a[m].type=1,a[m].id=i;
++m;a[m].sx=a[m].ty=tx,a[m].sy=a[m].ty=ty,a[m].u=v+eps,a[m].v=v+d,a[m].type=1,a[m].id=i;
++m;a[m].sx=sx,a[m].sy=sy,a[m].tx=tx,a[m].ty=ty,a[m].u=u,a[m].v=v,a[m].type=2,a[m].id=i;
++ans;
}
}
for (int i=1;i<=m;++i)
for (int j=i+1;j<=m;++j)
if (check(a[i], a[j]))
buc[a[i].id][a[j].id] = 1;
for (int i = 1; i <= n * 2; i++)
for (int j = 1; j < i; j++)
if (buc[i][j] || buc[j][i])
ans++;
printf("%d\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3928kb
input:
2 1 1 1 1 1 2 1 2 2 3
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
2 1 1 1 1 1 2 1 3 2 3
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 5900kb
input:
2 1 1 1 3 3 2 2 5 5 5 1 2 4
output:
2
result:
wrong answer 1st numbers differ - expected: '3', found: '2'