QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#125240#6734. Click the CirclejeroenodbWA 63ms3724kbC++174.8kb2023-07-16 08:49:502023-07-16 08:49:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-16 08:49:52]
  • 评测
  • 测评结果:WA
  • 用时:63ms
  • 内存:3724kb
  • [2023-07-16 08:49:50]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
typedef complex<ld> pt;
#define X real()
#define Y imag()
auto cross(pt u, pt v) {return (ld)u.X*v.Y-(ld)u.Y*v.X;}
auto sgn(ld a) {return a==0?0:(a>0?1:-1);}
auto ccw(pt p1, pt p2, pt p3) {auto u = p2-p1, v = p3-p2;return cross(u,v);}
auto in(pt p1, pt p2) {return (ld)p1.X*p2.X+(ld)p1.Y*p2.Y;}
auto norm(pt p) {return (ld)p.X*p.X+(ld)p.Y*p.Y;}
bool comp(const pt& a, const pt& b) { return a.X<b.X or (a.X==b.X and a.Y < b.Y);}
void read(pt& p) {
    int a,b; cin >> a >> b;
    p = {a,b};
}
struct circle {
    pt from, to;
    ld l,r;
    auto small(ld a, ld b) const {
        a=max(a,l);
        b=min(b,r);
        if(a>b) return circle{oo,oo,a,b};
        if(l==r) {
            return circle{from,from,a,b};
        }
        auto v = to-from;
        return circle{from+v*((a-l)/(r-l)), from+v*((b-l)/(r-l)),a,b};
        
    }
    void flip() {
        l=-l,r=-r;
        swap(l,r);
        swap(from,to);
    }
};
ld R,d;
bool intersect(ld a, ld b, ld c, ld d) {
    a= max(a,c);
    b = min(b,d);
    return a<=b;
}

bool segseg(pt p, pt q, pt a, pt b) { // strict segment segment intersection
    return sgn(ccw(p,q,a))*sgn(ccw(p,q,b))==-1 and sgn(ccw(a,b,p))*sgn(ccw(a,b,q))==-1;
}
bool segdist(pt l, pt r, pt a, pt b) {
    if(segseg(a,b,l,r)) return 1;
    for(int rep=0;rep<2;++rep) {
        for(auto p : {l,r}) {
            auto cur = min(norm(p-a),norm(p-b));
            if(cur<=R*R*(1 + 1e-15L)) return true;
            pt v = b-a, w = p-a;
            if(norm(v)>=1e-15) {
                if(in(v,w)>0 and in(v,w)<in(v,v)) {
                    if( R*R*(1 + 1e-15L)*norm(v) >= cross(v,w)*cross(v,w)) return true;
                }
            }
        }
        swap(l,a);
        swap(r,b);
    }
    return false;
}
bool checkCL(circle c, circle l) {
    if( intersect(c.l-d,c.l,l.l,l.r) ) {
        if(segdist(c.from,c.from,l.from,l.to)) return true;
    }
    if(intersect(c.l,c.r,l.l,l.r)) {
        auto myc = c.small(l.l,l.r);
        if(segdist(myc.from,myc.to,l.from,l.to)) return true;
    }
    if(intersect(c.r,c.r+d,l.l,l.r)) {
        if(segdist(c.to,c.to,l.from,l.to)) return true;
    }

    return false;
}
bool checkLL(circle c, circle l) {
    if( intersect(l.l,l.r, c.l,c.r) ) {
        if(segdist(c.from,c.to,l.from,l.to)) return true;
    }

    return false;
}
bool checkCC(circle c, circle o) {
    for(int _=0;_<2;++_) {
        for(int rep=0;rep<2;++rep) {
            if(rep==0 and intersect(c.l-d,c.l, o.l-d,o.l) ) {
                if(segdist(c.from,c.from,o.from,o.from)) return true;
            }
            if(intersect(c.l-d,c.l,o.l,o.r)) {
                auto myo = o.small(c.l-d,c.l);
                if(segdist(c.from,c.from,myo.from,myo.to)) return true;
            }
            if(rep==0 and intersect(c.l-d,c.l,o.r,o.r+d)) {
                if(segdist(c.from,c.from,o.to,o.to)) return true;
            }

            swap(c,o);
        }
        c.flip(),o.flip();
    }

    if(intersect(c.l,c.r,o.l,o.r)) {
        auto myc = c.small(o.l,o.r);
        auto myo = o.small(c.l,c.r);
        if(segdist(myc.from,myc.to,myo.from,myo.to)) return true;
    }
    return false;
}
int main() {
    vector<circle> cs;
    vector<circle> ls;
    int n;
    cin >> n >> R >> d;
    R*=2;
    for(int i=0;i<n;++i) {
        int tp; cin >> tp;
        if(tp==1) {
            pt p; read(p);
            ld t; cin >> t;
            cs.push_back(circle{p,p,t,t});
        } else {
            pt from,to;
            read(from), read(to);
            ld u,v; cin >> u >> v;
            cs.push_back(circle{from,to,u,v});
            ls.push_back(circle{from,to,u-d,v+d});
        }
    }

    int ans=0;
    for(auto c : cs) {
        for(auto l : ls) {
            ans+=checkCL(c,l);
        }
    }
    for(int i=0;i<cs.size();++i) {
        for(int j=0;j<i;++j) {
            ans+=checkCC(cs[i],cs[j]);
        }
    }
    for(int i=0;i<ls.size();++i) {
        for(int j=0;j<i;++j) {
            ans+=checkLL(ls[i],ls[j]);
        }
    }
    cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3524kb

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

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

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

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

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: 63ms
memory: 3724kb

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:

24133

result:

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