QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#751373 | #6734. Click the Circle | XfJbUhpyzgaW# | WA | 553ms | 4220kb | C++17 | 3.5kb | 2024-11-15 18:22:00 | 2024-11-15 18:22:00 |
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 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 (a[i].id!=a[j].id){
// printf("%d %d : ",i,j);
ans+=check(a[i],a[j]);
// printf(" %d \n",ans);
}
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3912kb
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: 3836kb
input:
2 1 1 1 1 1 2 1 3 2 3
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
2 1 1 1 3 3 2 2 5 5 5 1 2 4
output:
3
result:
ok 1 number(s): "3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
2 1 1 2 1 1 1 5 2 4 2 5 5 5 1 2 4
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
2 1 1 2 10 1 10 20 2 4 2 1 10 20 10 2 4
output:
6
result:
ok 1 number(s): "6"
Test #6:
score: -100
Wrong Answer
time: 553ms
memory: 4220kb
input:
1000 8 4 1 8323 2820 943 1 8246 2850 944 1 8177 2880 941 1 8154 2866 944 2 8325 8146 2865 2846 943 944 1 8349 2891 939 2 8176 8344 2888 2692 940 945 1 8191 2732 945 1 8144 2668 945 2 8182 8191 2889 2844 939 940 1 8173 2687 941 1 8241 2870 945 2 8266 8344 2910 2667 942 943 1 8169 2863 939 1 8349 2921...
output:
34019
result:
wrong answer 1st numbers differ - expected: '22721', found: '34019'