QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#421836 | #3183. Blowing Candles | juancs# | AC ✓ | 55ms | 9840kb | C++20 | 3.3kb | 2024-05-26 06:56:27 | 2024-05-26 06:56:27 |
Judging History
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'