QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#751402#6734. Click the CircleXfJbUhpyzgaW#WA 559ms20508kbC++173.6kb2024-11-15 18:28:292024-11-15 18:28:29

Judging History

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

  • [2024-11-15 18:28:29]
  • 评测
  • 测评结果:WA
  • 用时:559ms
  • 内存:20508kb
  • [2024-11-15 18:28:29]
  • 提交

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 + n;
            //++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: 3972kb

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: 3848kb

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: 3924kb

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: 1ms
memory: 5892kb

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: 1ms
memory: 6016kb

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: 559ms
memory: 20508kb

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:

29099

result:

wrong answer 1st numbers differ - expected: '22721', found: '29099'