QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#421836#3183. Blowing Candlesjuancs#AC ✓55ms9840kbC++203.3kb2024-05-26 06:56:272024-05-26 06:56:27

Judging History

This is the latest submission verdict.

  • [2024-05-26 06:56:27]
  • Judged
  • Verdict: AC
  • Time: 55ms
  • Memory: 9840kb
  • [2024-05-26 06:56:27]
  • Submitted

answer

#include <bits/stdc++.h>
#define el '\n'
#define forn(i, n) for(int i = 0; i < (int)n; ++i)
#define for1(i, n) for(int i = 1; i <= (int)n; ++i)
#define fore(i, l, r)for(int i = l; i <= (int)r; ++i)
#define fored(i, l, r)for(int i = r; i >= (int)l; --i)
#define all(a) a.begin(), a.end()
#define d(x) cerr<<#x<<" "<<x<<el
#define sz(x) x.size()
#define pb push_back
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef double ld;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef array<int, 4> a4;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;

const int nax = 1e4 + 100;
const ld inf = 1e17;
struct pt{
    ll x, y;
    pt(){}
    pt(ll x,ll y):x(x),y(y){}
    ll operator%(pt p){return x * p.y - y * p.x;}
    ll operator*(pt p){return x * p.x + y * p.y;}
    pt operator-(pt p){return {x - p.x, y-p.y};}
    ll norm2(){return *this**this;}
    ld norm(){return sqrt(norm2());}
    bool operator<(pt p)const{
        return x == p.x ? y < p.y : x < p.x;
    }
    bool operator ==(pt p)const{
        return x == p.x && y == p.y;
    }
    ll side(pt p, pt q){return (q-p) % (*this-p);}

};
const ld one = 1.0;
struct line
{
    pt v; ll c;
    line(){}
    line(pt p, pt q):v(q-p), c(v%p){}
    ll side(pt p){return v%p -c;}
    ld dist(pt p){assert(v.norm2() != 0); return abs(one*side(p) / v.norm());}
    ld distReal(pt p){return abs(one*side(p) / v.norm());}
};

vector<pt> chull(vector<pt> &p){
    if(sz(p) < 3) return p;
    vector<pt> r;
    sort(all(p));
    forn(i,sz(p)){
        while(sz(r) > 1 && r.back().side(r[sz(r)-2], p[i])>=0) r.pop_back();
        r.pb(p[i]);
    }
    r.pop_back();
    int k = sz(r);
    fored(i, 0, sz(p) -1){
        while(sz(r) > k + 1 &&r.back().side(r[sz(r)-2], p[i])>=0) r.pop_back();
        r.pb(p[i]);
    }
    r.pop_back();
    return r;
}

ld solve(vector<pt> &pts){
    int n = sz(pts);
   if(n <= 2)return 0;
    int j = -1;
    ld minDist = inf;
    line curline(pts[0], pts[1]);
    line minLine = curline;
    int minInd = -1;
    fore(i,2,n-1){
        ld di = curline.dist(pts[i]);
        if(j == -1 || di > curline.dist(pts[j])){
            j = i;
        }
    }
    minInd = j;
    minDist = curline.dist(pts[j]);
    fore(i,1, n-1){
        curline = line(pts[i], pts[(i+1) % n]);
        while(curline.dist(pts[(j-1+n)%n]) > curline.dist(pts[j]) || curline.dist(pts[(j+1)%n]) > curline.dist(pts[j]) ){
            if(curline.dist(pts[(j-1+n)%n]) > curline.dist(pts[(j+1+n)%n])){
                j = (j-1+n)%n;
            }else{
                j = (j + 1) % n;
            }
        }
        ld di = curline.dist(pts[j]) ;
        if(di < minDist){
            minDist = di;
            minLine = curline;
            minInd = j;
        }
    }
assert(minInd != -1);
    return minLine.distReal(pts[minInd]);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.precision(21);
    int n, r;
    cin >> n >> r;
    vector<pt> pts(n);
    forn(i,n){
        int x,y;
        cin>>x>>y;
        pts[i] = {x,y};
    }
    sort(all(pts));

    vector<pt> ch = chull(pts);

    ch.erase(unique(all(ch)), ch.end());
    // for(auto [x,y] : ch){
    //     cout<<x<<" "<<y<<")"<<el;
    // }
    ld ans = solve(ch);
    cout<<ans<<el;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3864kb

input:

3 10
0 0
10 0
0 10

output:

7.07106781186547461715

result:

ok found '7.07107', expected '7.07107', error '0.00000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

4 100
0 0
2 2
1 1
1 5

output:

1.56892908110547235623

result:

ok found '1.56893', expected '1.56893', error '0.00000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

4 100
0 0
-2 2
-1 1
-5 1

output:

1.56892908110547235623

result:

ok found '1.56893', expected '1.56893', error '0.00000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

4 100
0 0
-2 -2
-1 -1
-1 -5

output:

1.56892908110547235623

result:

ok found '1.56893', expected '1.56893', error '0.00000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

4 100
0 0
2 -2
1 -1
5 -1

output:

1.56892908110547235623

result:

ok found '1.56893', expected '1.56893', error '0.00000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3916kb

input:

4 100
0 0
2 -2
1 -1
1 -5

output:

1.56892908110547235623

result:

ok found '1.56893', expected '1.56893', error '0.00000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

4 100
0 0
2 2
1 1
5 1

output:

1.56892908110547235623

result:

ok found '1.56893', expected '1.56893', error '0.00000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3928kb

input:

4 100
0 0
-2 2
-1 1
-1 5

output:

1.56892908110547235623

result:

ok found '1.56893', expected '1.56893', error '0.00000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

4 100
0 0
-2 -2
-1 -1
-5 -1

output:

1.56892908110547235623

result:

ok found '1.56893', expected '1.56893', error '0.00000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3932kb

input:

3 20
10 0
10 1
10 2

output:

0

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

3 20
10 0
10 2
10 1

output:

0

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3928kb

input:

3 20
10 1
10 0
10 2

output:

0

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

3 20
10 1
10 2
10 0

output:

0

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3920kb

input:

3 20
10 2
10 0
10 1

output:

0

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

3 20
10 2
10 1
10 0

output:

0

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

4 100
1 1
1 2
2 1
2 2

output:

1

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #17:

score: 0
Accepted
time: 26ms
memory: 9840kb

input:

159642 10000001
0 -10000000
0 10000000
9999999 4472
-9999999 -4472
9999999 -4472
-9999999 4472
9999998 6325
-9999998 -6325
9999998 -6325
-9999998 6325
9999997 7746
-9999997 -7746
9999997 -7746
-9999997 7746
9999996 8944
-9999996 -8944
9999996 -8944
-9999996 8944
9999995 10000
-9999995 -10000
9999995...

output:

19999998

result:

ok found '19999998.00000', expected '19999998.00000', error '0.00000'

Test #18:

score: 0
Accepted
time: 48ms
memory: 6292kb

input:

200000 200000000
-44688205 41976403
-33839845 29990058
-31711709 11730345
47374949 -87301387
88366817 84095012
18719148 -9530672
21317633 -5557360
-73266917 -5960533
-27326101 19621387
86286450 17667444
63943748 98704956
86174018 24493783
59901906 -25187148
35104828 -10000233
93129026 63144824
-5652...

output:

199994149.062393993139

result:

ok found '199994149.06239', expected '199994149.06239', error '0.00000'

Test #19:

score: 0
Accepted
time: 47ms
memory: 6344kb

input:

200000 200000000
-21722245 47249047
3745652 18507096
25288815 11982590
-70315255 -62453490
-70300814 -16869663
84335219 -82689738
-42406547 -88845871
-75147195 -69168189
-72109075 41293273
-63826547 -62603953
16241675 77805523
59364926 22486411
19338940 -27908233
91240467 6899258
-97814572 34690208
...

output:

199997471.62310603261

result:

ok found '199997471.62311', expected '199997471.62311', error '0.00000'

Test #20:

score: 0
Accepted
time: 55ms
memory: 6156kb

input:

200000 200000000
95049215 30688972
-45277904 22437968
-73293137 33923272
30223549 54244476
25199933 87238859
49062903 -41383484
-87731675 76744319
90637696 37076366
-8871363 81411906
-6591136 -30519973
34063981 -38995939
63153676 22816043
67667151 98817206
-61667198 90130567
-58409293 23156835
-5614...

output:

199997197.126268297434

result:

ok found '199997197.12627', expected '199997197.12627', error '0.00000'

Test #21:

score: 0
Accepted
time: 51ms
memory: 6384kb

input:

200000 200000000
-5731582 -25614801
-29580993 -67063995
-13729701 -45474895
39422127 -57302146
33062038 41691433
-97744986 1472243
-63278879 -43354258
6493471 -21835147
44663767 62678874
32167994 93865049
-92006486 25647031
-79600488 -70967485
51050213 -68615014
-50958616 36896692
42753963 16752922
...

output:

199995772.838815450668

result:

ok found '199995772.83882', expected '199995772.83882', error '0.00000'

Test #22:

score: 0
Accepted
time: 52ms
memory: 6344kb

input:

200000 200000000
-68427956 -66643590
50290435 67146136
90455718 94955610
72881956 4099369
91338021 39474232
-58068198 -59351775
30557841 -96987494
85884434 65624924
35236518 -77940367
13494835 -98383373
57639571 28148087
-84355557 16928766
11865908 -8593835
-50594003 -17973658
-29956039 -70062037
-4...

output:

199997226.194480478764

result:

ok found '199997226.19448', expected '199997226.19448', error '0.00000'

Test #23:

score: 0
Accepted
time: 52ms
memory: 6280kb

input:

200000 200000000
-60435657 -36857470
-9357928 82707300
-31307662 -25591697
-59037919 -40252597
33693631 18082719
-71506737 30432033
-23857680 -17265964
-14539340 -19320466
17269792 -34055941
17000726 -58064093
17008359 -5293956
3008341 -39882600
-9171619 -74408808
-89524827 -31848255
63231912 -90769...

output:

199998606.672401040792

result:

ok found '199998606.67240', expected '199998606.67240', error '0.00000'